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

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&nbsp;countChange(money:&nbsp;Int,&nbsp;coins:&nbsp;List[Int]):&nbsp;Int&nbsp;= &nbsp;&nbsp;if&nbsp;(money&nbsp;==&nbsp;0)&nbsp;1 &nbsp;&nbsp;else&nbsp;if&nbsp;(coins.isEmpty&nbsp;||&nbsp;money&nbsp;<&nbsp;0)&nbsp;0 &nbsp;&nbsp;else&nbsp;countChange(money&nbsp;-&nbsp;coins.head,&nbsp;coins)&nbsp;+&nbsp;countChange(money,&nbsp;coins.tail)

Answer 3

我赞成递归解决方案。你有一些面额列表，如果最小的面额可以平均分配任何剩余的货币金额，这应该工作正常。基本上，您从最大面额移动到最小面额。递归，您有一个当前总数要填充，以及一个最大面额（剩下超过1个）。如果只剩下1个面额，那么只有一种方法可以填补总数。您可以使用当前面额的0到k个副本，使得k * cur面额<=总计。对于0到k，使用修改的总计和新的最大面额调用函数。将结果从0添加到k。这就是你可以用多少种方式从目前的面额中填补总数。返回此号码。这是我所说的问题的python版本，200美分。我得到了1463种方式。此版本打印所有组合和最终计数总数。#!/usr/bin/python#&nbsp;find&nbsp;the&nbsp;number&nbsp;of&nbsp;ways&nbsp;to&nbsp;reach&nbsp;a&nbsp;total&nbsp;with&nbsp;the&nbsp;given&nbsp;number&nbsp;of&nbsp;combinationscents&nbsp;=&nbsp;200denominations&nbsp;=&nbsp;[25,&nbsp;10,&nbsp;5,&nbsp;1]names&nbsp;=&nbsp;{25:&nbsp;"quarter(s)",&nbsp;10:&nbsp;"dime(s)",&nbsp;5&nbsp;:&nbsp;"nickel(s)",&nbsp;1&nbsp;:&nbsp;"pennies"}def&nbsp;count_combs(left,&nbsp;i,&nbsp;comb,&nbsp;add): &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;add:&nbsp;comb.append(add) &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;left&nbsp;==&nbsp;0&nbsp;or&nbsp;(i+1)&nbsp;==&nbsp;len(denominations): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(i+1)&nbsp;==&nbsp;len(denominations)&nbsp;and&nbsp;left&nbsp;>&nbsp;0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;left&nbsp;%&nbsp;denominations[i]: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;comb.append(&nbsp;(left/denominations[i],&nbsp;demoninations[i])&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;+=&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;i&nbsp;<&nbsp;len(denominations): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;comb.append(&nbsp;(0,&nbsp;denominations[i])&nbsp;) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;+=&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print("&nbsp;".join("%d&nbsp;%s"&nbsp;%&nbsp;(n,names[c])&nbsp;for&nbsp;(n,c)&nbsp;in&nbsp;comb)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;cur&nbsp;=&nbsp;denominations[i] &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;sum(count_combs(left-x*cur,&nbsp;i+1,&nbsp;comb[:],&nbsp;(x,cur))&nbsp;for&nbsp;x&nbsp;in&nbsp;range(0,&nbsp;int(left/cur)+1))count_combs(cents,&nbsp;0,&nbsp;[],&nbsp;None)