如果给出一些美元价值，如何找到所有硬币组合

Question

如果给出一些美元价值，如何找到所有硬币组合几个月前，我找到了一段代码，我正在编写面试。根据我的评论，它试图解决这个问题：给定一美分的美分价值（例如200 = 2美元，1000 = 10美元），找到构成美元价值的所有硬币组合。只有便士（1¢），镍（5¢），角钱（10¢）和四分之一（25¢）。例如，如果给出100，答案应该是：4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies  3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies  etc.我相信这可以通过迭代和递归方式解决。我的递归解决方案非常错误，我想知道其他人如何解决这个问题。这个问题的难点在于尽可能提高效率。

Answer 1

我很久以前就研究了这个问题，你可以读一下我的小文章。这是Mathematica的来源。

通过使用生成函数，您可以获得问题的封闭形式的恒定时间解决方案。格雷厄姆，克努特和帕塔什尼克的混凝土数学就是这本书的书，并且对这个问题进行了相当广泛的讨论。基本上，您定义了一个多项式，其中第n个系数是以n美元进行更改的方式的数量。

这篇文章的第4-5页显示了如何使用Mathematica（或任何其他方便的计算机代数系统）在三行代码中在几秒内计算10 ^ 10 ^ 6美元的答案。

（而且这已经很久以前在75Mhz Pentium上只有几秒钟......）

Answer 2

注意：这仅显示方式的数量。

Scala功能：

def countChange(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (coins.isEmpty || money < 0) 0
  else countChange(money - coins.head, coins) + countChange(money, coins.tail)

Answer 3

我赞成递归解决方案。你有一些面额列表，如果最小的面额可以平均分配任何剩余的货币金额，这应该工作正常。

基本上，您从最大面额移动到最小面额。
递归，

1. 您有一个当前总数要填充，以及一个最大面额（剩下超过1个）。如果只剩下1个面额，那么只有一种方法可以填补总数。您可以使用当前面额的0到k个副本，使得k * cur面额<=总计。

2. 对于0到k，使用修改的总计和新的最大面额调用函数。

3. 将结果从0添加到k。这就是你可以用多少种方式从目前的面额中填补总数。返回此号码。

这是我所说的问题的python版本，200美分。我得到了1463种方式。此版本打印所有组合和最终计数总数。

#!/usr/bin/python# find the number of ways to reach a total with the given number of combinationscents = 200denominations = [25, 10, 5, 1]names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
           if left % denominations[i]:
               return 0
           comb.append( (left/denominations[i], demoninations[i]) )
           i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))count_combs(cents, 0, [], None)