algorithm - 采访 : Making change for n cents (arbitrary denominations)

Question

这个问题是面试中难度越来越大的问题的一部分。它的开始非常简单:

(1) Assuming an infinite supply of coins (in the usual 1, 5, 10, 25 cent denominations). Given n cents, is there always a way to make change for it using the normal denominations?

是的，因为一分钱可以划分所有可能的 n 分值。

(2) Good, now write a program that accepts n (positive) cents, and returns one possible way of making change for it

返还 n 个便士。

(3) Smart ass. What if you want to minimize the number of coins required to make the change?

从最大的面额 d_i 开始，取最大数量，这样您就不会超过 n，m_i。取 n - (d_i)(m_i) 并重复下一个最大的面额。

(4) Good, can you prove this solution is optimal?

是的，{等等，等等}

(5) Ok, *smirk* , now what if, in addition to the n cents, you were given an arbitrary-sized array consisting of arbitrary denominations? You can assume each denomination occurs only once in the array, and that all denominations are positive

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

我的下一个想法是将求和子集问题应用于 n 的每个除数，但意识到这可能有点矫枉过正。我最终提供的解决方案只使用了 Change-making problem ，并在我找到一些解决方案时将其短路。不过，我觉得必须有一种更聪明的方法来做到这一点..

问题简化为:给定一个由不同自然数组成的有限集 S，找到 S 元素的线性组合，使 (1) 与另一个相加自然数n, (2) 最小化lin.combination中的系数之和

Answer 1

实际上这个问题已经作为Canonical coin systems 进行了研究，我们甚至得到了一篇关于如何确定给定的硬币系统是否可以支持贪婪解决方案的论文。原始论文可能会给您一些见解:Canonical coin systems for change-making problems .

或者，您可以在谷歌上搜索关键词“Canonical coin systems”以获取更多信息。