確定一美元金額的最佳硬幣組合

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以用於下一次迭代。

請注意，該算法適用於您所指的一般情況。對於任何其他的硬幣系統，每個硬幣都是其後的硬幣（世界上大多數投幣系統）的除數 - 貪婪解決方案是最簡單的，並且是最優的。