我正在尝试编写一个函数来查找产生指定金额的所有可能的硬币组合,例如它计算所有可能的方式来从1p,2p,5p,10p的面额列表中更改2英镑的金额, 20P,50P,1pound,2pound . 我坚持这个,找不到合适的解决方案 .
我希望main函数是递归的,因为我想更好地理解递归 . 该算法必须回溯,如果在某个时刻发现的组合超过了要匹配的量,则程序应该返回到先前的步骤并从不同的点开始 .
到目前为止,我已经编写了一个普通(非递归)函数,如果每个硬币仅使用一次,则计算给定国家中所有可能的硬币组合(这相当简单) . 我并没有试图找到一个给定数额的正确组合,只是所有可能的硬币组合 .
def calcCoins(coins):
"""
returns all possible combinations of coins, when called with
[1,2,5,10,20,50,100,200] returns a list of 126 Counters containing
for instance Counter{1:1}, Counter{1:1,2:1,5:1}, Counter {50:1,100:1} etc
"""
i,combs = 1, []
while i < len(coins):
for x in combinations(coins,i):
combs.append(Counter(x))
i += 1
return combs
现在我有一个笨拙的递归函数,它接受一个组合和所需的数量作为参数,并返回所有可能的方式,其中可以给出等于此数量的更改 .
def findSum(comb,goal,rightOnes):
if rightOnes == None:
rightOnes = []
if sum(comb.elements()) == goal:
comb_ = Counter(comb)
if comb_ in rightOnes:
# probably a cycle, return combinations gathered and exit
return rightOnes
rightOnes.append(comb_)
elif sum(comb.elements()) > goal:
#this is meant to be backtracking
return False
for k in comb:
comb[k] += 1
if findSum(comb,goal,rightOnes) != False:
return findSum(comb,goal,rightOnes)
else:
comb[k] = 1
return rightOnes
对于非常小的组合,该函数运行并正确返回:对于
test2 = Counter({10: 1, 20: 1})
findSum(test2,200,[])
它返回:
[Counter({10: 18, 20: 1}), Counter({10: 16, 20: 2}),
Counter({10: 14, 20: 3}), Counter({10: 12, 20: 4}),
Counter({10: 10, 20: 5}), Counter({10: 8, 20: 6}),
Counter({20: 7, 10: 6}), Counter({20: 8, 10: 4}),
Counter({20: 9, 10: 2})]
但对于较大的,如
test3 = Counter({1: 1, 2: 1, 10: 1})
test4 = Counter({1: 1, 2: 1, 100: 1, 10: 1})
它超过了递归的限制 . 它运行正常,直到某个时刻,打印出部分结果,但在某些时候它超过了最大递归深度 .
我正在制造哪些错误让这个功能无法正常运行?这是我实现回溯的原因吗?我省略了一些案例吗?如何优化此功能,使其不超过最大递归深度?
提前致谢!
编辑:这是追溯:
if findSum(comb,goal,rightOnes) != False:
File "C:\playground\python\problem31.py", line 105, in findSum
if sum(comb.elements()) == goal:
File "C:\Python27\lib\collections.py", line 459, in elements
return _chain.from_iterable(_starmap(_repeat, self.iteritems()))
RuntimeError: maximum recursion depth exceeded while calling a Python object
和最后一个部分结果,就在函数中断之前(用test3调用)
[Counter({1: 163, 2: 1, 20: 1, 10: 1, 5: 1}), Counter({1: 161, 2: 2, 20: 1, 10: 1, 5: 1}),
Counter({1: 159, 2: 3, 20: 1, 10: 1, 5: 1}), Counter({1: 157, 2: 4, 20: 1, 10: 1, 5: 1}),
Counter({1: 155, 2: 5, 20: 1, 10: 1, 5: 1}), Counter({1: 153, 2: 6, 20: 1, 10: 1, 5: 1})]
1 回答
首先,正如this question的第一个答案所示,由于Python作为一种语言的语义,递归并不是一种特别有效的范例 . 但是,正如在那里指出的那样,可以使用
sys.setrecursionlimit(2000)
. (或者你需要多少)我想强调这是"lazy"解决方案,我强烈建议使用你的第一个(非递归)版本 .