指定された金額を生み出すコインのすべての可能な組み合わせを見つける関数を作成しようとしています。たとえば、金種 1p、2p、5p、10p、 20p、50p、1ポンド、2ポンド。私はこれで立ち往生しており、正しい解決策を見つけることができません。
再帰をよりよく理解したいので、メイン関数を再帰的にしたいと考えています。ある瞬間に見つかった組み合わせが一致する量を超えた場合、アルゴリズムはバックトラックする必要があり、プログラムは前のステップに戻って別のポイントから開始する必要があります。
これまでのところ、各コインが 1 回しか使用されない場合に、特定の国で考えられるすべてのコインの組み合わせを計算する通常の (再帰的ではない) 関数を作成しました (これはかなり単純です)。コインのすべての可能な組み合わせだけで、特定の合計に適した組み合わせをまだ見つけようとはしていません。
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})]