javascript - 确定一美元的最佳硬币组合

Question

我需要找到构成一定金额的硬币的最佳组合。所以本质上，我想用最少的硬币到达那里。

例如：

如果货币系统有硬币：{13, 8, 1}，贪心解决方案会将 24 的零钱变为 {13, 8, 1, 1, 1}，但真正的最优解决方案是 {8, 8, 8} .

我希望用 Javascript 编写它，但是伪代码很好，因为我确信这会帮助更多的人。

Answer 1

一般来说，这个问题实际上是 NP 完全的（参见Change-making problem）。但是，对于很多货币系统（包括美国的 {1, 5, 10, 25} 系统），贪心算法也恰好是最优的。

Answer 2

这个问题叫动态编程。

基本的伪代码应该是这样的：

• 令C(n)为用于和n的最小硬币数。
• 在每个递归步骤中，找到下一个最大值硬币c，并选择C(n)为：
• C(nc)+1（使用所述硬币，更新使用的总硬币和剩余值）和C(n) （不使用硬币）之间的最小值- 在这两种情况下，从可用硬币列表中删除c下一次迭代。

请注意，此算法适用于您所指的一般情况。对于任何其他硬币系统，每个硬币都是其后一个硬币的除数（世界上大多数硬币系统） - 贪婪解决方案是最简单的，也是最优的。