因此，这是一个涉及硬币的两部分问题。第一部分涉及对总计为1-99美分的硬币计数求和（例如，需要花费1枚硬币达到1美分，花费2枚硬币达到2美分，依此类推，然后将获得的硬币总和相加每个值）。这可以由以下代码表示（可以提出建议/改进）：
def findbest(origarray, denom):
current = origarray
i = 1
while(i < size):
if(i in denom):
current[i] = 1
coinlist[i] = [i]
else:
k = 1
while(k < 1 + (i/2)):
c = current[k] + current[i-k]
if(c < current[i]):
current[i] = c
coinlist[i] = coinlist[k] + coinlist[i-k]
k+=1
print i, current[i], coinlist[i]
i+=1
return current
size = 100
coinlist = [[]]
origarray = [0]
i = 1
while(i < size):
origarray.append(100)
coinlist.append([])
i += 1
denom = [1,5,10,25,50]
x = findbest(origarray, denom)
total=0
for value in findbest(origarray,denom):
total += value
print total
print "\n\n\n"
print x
问题的第二部分是找到理想的三种面额（不必是真实面额，但必须是1个面额），这将使所有硬币总数最低。
这对我来说很棘手。我知道我必须写一些东西将对面额值进行暴力破解，直到找到最优的三个面额（我知道是[1,12,19]，我只是无法达到这一点），但是我不是确定如何去做。有谁知道如何做到这一点？
最佳答案
您正在寻找的功能，将使这完全是琐碎的是itertools.combinations。
>>> from itertools import combinations
>>> len(list(a for a in combinations(range(1, 101), 3)))
161700
我建议基于您的实现，如下所示：
def findbest(origarray, denom):
current = origarray
i = 1
while(i < size):
if(i in denom):
current[i] = 1
coinlist[i] = [i]
else:
k = 1
while(k < 1 + (i/2)):
c = current[k] + current[i-k]
if(c < current[i]):
current[i] = c
coinlist[i] = coinlist[k] + coinlist[i-k]
k+=1
#print i, current[i], coinlist[i]
i+=1
return current
size = 100
def reset_cache():
i = 1
global coinlist
coinlist = [[]]
global origarray
origarray = [0]
while(i < size):
origarray.append(100)
coinlist.append([])
i += 1
reset_cache()
denom = [1,5,10,25,50]
x = findbest(origarray, denom)
total=0
for value in findbest(origarray,denom):
total += value
print total
print "\n\n\n"
print x
from itertools import combinations
best = ((0,0,0), 1e6)
for comb in combinations(range(1, 101), 3):
#print "Considering: %s" % comb
reset_cache()
total = 0
for value in findbest(origarray, comb):
total += value
if total < best[1]:
print "%s beat best with %d" % (comb, total)
best = (comb, total)
print best
但是我需要一个我认为是硬币缓存的麻烦吗？我不确定，我没有太认真地阅读您的代码。但是我不喜欢传递一些数组来使其工作的必要性。它应该是独立的。
编辑：对我来说，你实际上可以逃脱
for comb in [(1,) + a for a in combinations(range(2, 101), 2)]:
因为任何有效的找零系统都需要拥有1美分的硬币。这使代码运行更快，因为
>>> len([(1,) + a for a in combinations(range(2, 101), 2)])
4851
关于python - 寻找最低硬币总额的最佳变化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19625109/