确定一美元金额的最佳硬币组合

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）是用于总和为ň硬币的数量降到最低。
• 在每一递归步骤中，找到下一个极大值的硬币，Ç，并选择C（n）的是：
• 所述硬币C（NC）1之间的最小值（使用更新所使用的总硬币和剩余价值）和C（n）（不使用硬币） - 在两种情况下，从可用硬币列表中删除c以用于下一次迭代。

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