所以这是一个涉及硬币的两部分问题。第一部分涉及将金额为 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
