Skip to main content
 首页 » 编程设计

python之寻找最低硬币总数的最佳变化

2024年11月01日10dflying

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