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

Question

所以这是一个涉及硬币的两部分问题。第一部分涉及将金额为 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]，我只是无法达到那个点)，但我不是确定如何去做。有谁知道如何做到这一点？

Answer 1

您正在寻找的函数是 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