將如何在這種硬幣找零情況下，貪婪的工作

說我有隻25美分，10美分和4美分硬幣和我的總量是41.使用貪心，我將選擇25美分，然後10美分，然後剩下的6美分不能製造。

所以我的問題是，在這種情況下貪婪會告訴我，有沒有解決方案？

2014-01-15 Kraken

我不明白你的問題。顯然，貪婪算法告訴你沒有解決方案，因爲當你應用它時，你會發現......沒有解決方案。 – GreenAsJade

它看起來像你的問題是正確的貪婪算法維基回答：http://en.wikipedia.org/wiki/Greedy_algorithm#Cases_of_failure

想象一下，只有25美分，10美分和4美分硬幣硬幣的例子。貪婪的算法不能夠改變41美分，因爲在承諾使用一個25美分硬幣和一個10美分硬幣之後，不可能使用4美分硬幣剩餘6美分，而一個人或者更復雜的算法可以用一個25分硬幣和4個4分硬幣改變41美分。

2014-01-15 11:12:56 esel

我其實從其他一些鏈接中得到了它，但是，我希望知道Greedy是否會嘗試找到解決方案，或者它是否遵循單一路徑，如果成功，那麼就很好，否則它只會給出向上。謝謝:) – Kraken

@Kraken貪婪，最簡單的形式，沒有任何形式的回溯。所以這只是「一杆」。在這種情況下，它將無法提供解決方案。 – esel

鏈接中提到的貪婪算法假定存在單位硬幣。否則有一些它根本無法處理的整數量。

關於最優性 - 如上所述，它取決於可用的硬幣。例如，對於{10,5,1}，貪婪算法總是最優的（即返回要使用的最小數量的硬幣）。對於{1,3,4}貪婪算法不保證是最優的（它返回6 = 4 + 1 + 1而不是6 = 3 + 3）。

2014-01-15 11:12:47

看來，貪婪算法並不總是最好的，這種情況下作爲例子來說明，當它不能在維基百科

工作

2014-01-15 11:13:35

回答