2

所以这是一个涉及硬币的两部分问题。第一部分涉及将 1-99 美分的硬币数量相加（例如，需要 1 个硬币才能达到 1 美分，2 枚硬币才能达到 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]，我只是无法达到那个点），但我不是确定如何去做。有谁知道如何做到这一点？

4

2 回答 2

1

我的java版本

public static int minChange(int[] coins, int total) {
        int[] counts = new int[total + 1];
        counts[0] = 0;
        int MAX = Integer.MAX_VALUE - 1;
        for (int i = 1; i <= total; ++i) {
            int count = MAX;
            for (int j = 0; j < coins.length; ++j) {
                if (i - coins[j] >= 0 && count > counts[i - coins[j]])
                    count = counts[i - coins[j]];
            }
            if (count < MAX)
                counts[i] = count + 1;
            else
                counts[i] = MAX;
        }
        return counts[total];
    }
于 2014-10-01T20:56:16.733 回答
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
于 2013-10-28T02:13:34.457 回答