采访：为n美分（任意面额）做零钱

Question

在一次采访中，这个问题是一个日益困难的问题的一部分。它的开始非常简单：

（1）假设有无限的硬币供应（通常的1, 5, 10, 25美分面额）。给定n美分，是否总有一种方法可以用正常面额进行兑换？

是的，因为便士除以所有可能的n美分。

（2） 很好，现在编写一个接受n（正）美分的程序，并返回一种可能的更改方法

归还n便士。

（3）聪明的屁股。如果您想最小化更改所需的硬币数量，该怎么办？

从最大面额的d_i开始，取最大数，这样就不会超过n，m_i。取n-（d_i）（m_i），然后重复下一个最大面额。

（4）好，你能证明这个解是最优的吗？

是的，{诸如此类，诸如此类}

（5） 好的，*傻笑*，现在，如果除了n美分之外，您还得到了一个由任意面额组成的任意大小的数组呢？您可以假设每个面额在数组中只出现一次，并且所有面额都是正数

我最初的想法是对面额数组进行排序，并应用与（4）中相同的逻辑。幸运的是，在我传达这一点之前，我意识到这是行不通的。但现在我意识到我陷入了困境。

我的下一个想法是将求和子集问题应用于n的每个除数，但意识到这可能有点过头了。我最终提供的解决方案只是使用了变更问题，当我找到一些解决方案时，它就短路了。我觉得必须有一个更聪明的方法。。

问题归结为：给定一个不同自然数的有限集S，找到S元素的线性组合，这些元素（1）与另一个自然数n求和，（2）使lin组合中的系数之和最小化

Answer 1

假设d[pos][sum]是只使用第一个pos符号或无限（如果不可能）来更改sum货币所需的最小硬币数

设a[i]是硬币i的去名词化

可以递归地理解。规则1）和2）将是递归的基础。

1）d[any pos][0]=0（我们可以在没有硬币中返回任何钱）

2）d[1][每个和]=if（a[1]！=和）无穷大其他1（我们可以通过一个硬币改变和只有当它有去名词<代码>和 ）

3）其他：

我们可以选择当前点进行更改或不选择它

d[pos][sum]=min（选择，d[pos-1][sum]）where

如果和的话，选择d[pos-1][和a[i]]

如果我们不选择硬币号pos，我们尝试用pos-1硬币做同样的改变。因此，d[pos-1][sum]

如果我们选择硬币号pos，那么我们只需要通过对pos的去名词化来改变总和小于当前的总和。d[pos-1][Sum-a[i]]

但我们只能选择硬币号码pos，只要它的表示小于或等于当前的总和

实际解决方案

a） 递归应该被循环所取代

或

b）我们应该存储是[pos][sum]-如果值d[pos][sum]被计算。

当我们尝试计数时，d[pos][sum]

如果是[pos][sum]==true就返回它。（该值已计数）

否则：按照步骤1-3进行计数，并将was[pos][sum]设置为true

Answer 2

有一个简单的答案，可以给出以n为单位的伪多项式时间和空间（即，运行时间和内存使用与n成正比，而不是与输入大小logn成正比），还有一个更难但更有用的答案，可以让您获得固定面额的真多项式时间。

做一个大小为n的数组A。这个数组存储了每个k=1到n产生k美分所需的最小硬币数，如果不可能产生k美分，则为A[k]=-1。你可以从k=1到n依次填充这个数组，如果k是你的一个面值，记录A[k]=1，否则记录A[k]=M 1，其中M是所有面值中A[k-C]的最小值C（和A[k]=-1如果所有的k-C不是正数have或A[k-C]=-1）。然后，一旦你达到n，你可以从n开始返回数组，减去每个面额，看看哪个面额给了你最佳答案，追溯所有用来形成最佳解的硬币。

这是一个简单的答案。现在，与面值相比，非常大的n的硬答案是弄清楚什么时候你可以走捷径，暂时拿走最大面值的硬币，直到剩余的美分降到某个价值以下。我不知道如何求解这个值，但是它是可能的，并且这个值总是存在的，一旦你计算出来，那么不管n有多大，你所要做的就是先计算出最大的硬币的数量（O（log n）时间），然后在低于该值时求解（如果您认为面额固定，则为恒定时间，如果面额不固定，则取决于面额（但不是n）的运行时间）。

Answer 3

实际上，这个问题已经被研究为规范硬币系统，我们甚至得到了一篇关于如何确定给定硬币系统是否支持贪婪解决方案的论文。原始论文可能会给你一些见解：用于变革问题的规范硬币系统。

或者，你可以谷歌关键词“规范硬币系统”获取更多信息。