最適合給定金額的最佳硬幣

如果給定一套硬幣，您會如何以最佳方式達到給定金額？最適合給定金額的最佳硬幣

假設在這種情況下，我們有隨機數字1，5，10，20和50分硬幣與最大的硬幣獲得優先權。

我的第一個直覺就是使用所有最大的硬幣來適應，然後如果總和超過，用完下一個最小的硬幣。

這樣做還是會有這種方法的不足嗎？有沒有更有效的方法？

來源

2012-10-01 James P.

我就是這樣做的。 – dutt

查看http://wcipeg.com/wiki/Dynamic_programming#Optimization_example:_Change_problem，它解釋了這個* exact *概念以及如何使用動態編程來解決這個問題。 –

您首先必須檢查是否給定了一組硬幣C（例如C = {1,5,10,20,50}）是規範的（或者在某些文章中是有序的）。如果是貪婪算法給出任何給定數量的最佳答案，如果不是，那麼你不得不在dp上回退以得到最佳答案 – Kwariz

簡單地首先給出最大的硬幣是有缺陷的。

假設您的自動售貨機除了50c，20c和1c兩種硬幣之外的每個硬幣，您必須提供60c的變化。

「優先級最大」（或貪婪）計劃會給你11個硬幣，一個50c硬幣和10個1c硬幣。

更好的解決方案是三個20C硬幣。

貪婪方案只給你本地最佳解決方案。對於全局最優化，通常需要檢查所有可能性（儘管可能會有最小類型算法來減少搜索空間），以確保對於傳遞變化，這通常在可計算性的限度內。

來源

2012-10-01 05:05:37 paxdiablo

Greedy Algorithms（你現在正在做什麼）通常選擇這種類型的東西，並實施爲Final State Machines用於自動售貨機（對於這種特殊情況）。

貪婪算法確定在進行更改時給予的最小硬幣數量。這些是人們用來模擬的步驟貪婪算法

來源

2012-10-01 05:01:37 npinti

值得注意的是，這確實假定硬幣的面值是智能選擇的 - 正如它們通常以實際貨幣計價。在*隨機*面值的情況下，這不能產生最好的選擇（參見@paxdiablo的50c/20c/1c的例子）。 –

@lc：確實。這是貪婪算法的侷限性。我帶來了自動售貨機的例子，因爲他們通常處理的數量相對較少。 – npinti

每次用盡最大面額的假設都不是最好的解決方案。例如：

Input: coins[] = {25, 10, 5}, V = 30 
Output: Minimum 2 coins required 
We can use one coin of 25 cents and one of 5 cents 

Input: coins[] = {9, 6, 5, 1}, V = 11 
Output: Minimum 2 coins required 
We can use one coin of 6 cents and 1 coin of 5 cents (min) 
As per logic of exhausting largest coins first, we would end up with one 
coin of 9 cents and 2 coins of 1 cent

請參閱this answer瞭解更多信息。

來源

2016-05-09 12:33:15

最適合給定金額的最佳硬幣

回答

相關問題