<分区>
问题是 here
假设我只有 25 美分、10 美分和 4 美分的硬币，我的总数是 41。使用贪心，我会选择 25 美分，然后是 10 美分，然后剩下的 6 美分不能制作。
所以我的问题是，在这种情况下贪婪会告诉我没有解决方案吗？
<分区>
问题是 here
假设我只有 25 美分、10 美分和 4 美分的硬币，我的总数是 41。使用贪心，我会选择 25 美分，然后是 10 美分，然后剩下的 6 美分不能制作。
所以我的问题是，在这种情况下贪婪会告诉我没有解决方案吗？
最佳答案
看起来你的问题在贪婪算法 wiki 中得到了正确的回答:http://en.wikipedia.org/wiki/Greedy_algorithm#Cases_of_failure
Imagine the coin example with only 25-cent, 10-cent, and 4-cent coins. The greedy algorithm would not be able to make change for 41 cents, since after committing to use one 25-cent coin and one 10-cent coin it would be impossible to use 4-cent coins for the balance of 6 cents, whereas a person or a more sophisticated algorithm could make change for 41 cents with one 25-cent coin and four 4-cent coins.
关于algorithm - 贪婪将如何在这个硬币找零的案例中发挥作用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21135723/