贪心算法在硬币找零问题中的坏情况是什么？

Question

硬币找零问题是指用最少的硬币找零n美分。您是否可以提供一组硬币面额，使得贪婪算法不能得出最优解？这个集合应该包括一美分，以便对于每个n都有解决方案。

- Anand

---

这个问题类似于一道作业的学校练习题。 - Albert Lazaro de Lara

我不会添加另一个答案，但是会提到在良好的货币系统中这是不可能发生的。这意味着对于像1、2、5、10、20、50等系统，贪心算法是最好的选择。 - xenteros

@xenteros 贪心算法在货币系统中即使是良好的情况下也可能失败，特别是当你没有无限的硬币或纸币时。请看下面的例子。这绝对看起来像是一道学校作业问题。我和儿子讨论了这个问题，花了一点时间才想出一个贪心解决方案不起作用的例子。 - AggieMan

Answer 1

好的，假设有 10, 7, 1 三种硬币，需要找零 15 元：

15 = 10 + 1 + 1 + 1 + 1 + 1 // greedy  (6 coins)
15 =  7 + 7 + 1             // optimal (3 coins)

你可以轻松地生成一种贪心解决方案，使其尽可能 低效： 只需将可用硬币设为 1、N-1、N，然后尝试找零 2 * N - 2。

 N, 1, 1, ..., 1 // greedy  (N - 1 coins)
 N-1, N-1        // optimal (2 coins)

现在，让N变得更大。

- Dmitry Bychenko

---

很好的回答，第一个例子非常清晰！然而，我认为最后一个例子不会导致低效情况，因为贪心算法会尝试：N + (N - 1) 而不是 N + 1 + 1 + ... + 1。此外，最优解将是 N + (N - 1)，即等于 2 * N - 1。我认为如果我们尝试改变 X，低效的解决方案将是在硬币中进行选择：floor(X/2) + 2, floor(X/2), 1。例如：X = 123，硬币将是：63、61、1。贪心解决方案将是：63 + 1 + 1 + ... + 1，而最优解决方案将是：61 + 61 + 1。 - mateleco

@mateleco：抱歉打错了，应该是要交换的总和为“2 * N-2”。 - Dmitry Bychenko

好的，在您的修改后，现在它讲得通了。然而，顺便提一下，如果我们试图找零一个奇数金额的钱，您的通用解决方案会导致十进制硬币。但是我并不是挑剔，只是为了记录而指出。感谢您的答案！ :) - mateleco

Answer 2

硬币：1、5、8
数量：10
贪心算法的解决方案：8、1、1（3枚硬币）
最优解：5、5（2枚硬币）

---

关于@xenteros的评论，请参阅维基百科（在那里，你会发现一个例子）：

对于所谓的经典硬币系统，如美国和许多其他国家使用的硬币系统，选择不大于剩余待做金额的最大面额硬币的贪心算法将产生最佳结果。但是，对于任意硬币系统来说，并非总是这样：如果硬币面额为1、3和4，则要制作6元，贪心算法会选择三枚硬币（4、1、1），而最优解是两枚硬币（3,3）。

- dingalapadum

Answer 3

贪心算法在硬币数量有限的情况下并不总是有效。假设你在现金出纳机里有以下金额：

• 50美元：3张钞票
• 10美元：11张钞票
• 5美元：6张钞票
• 1美元：9张钞票
• 25美分：55个硬币
• 10美分：47个硬币
• 5美分：没有
• 1美分：4个硬币

一位顾客购买价值69美分的糖果，用1美元纸币支付，并需要找回31美分的零钱。

贪心算法将首先选择一个25美分的硬币，然后还需要再选6美分的硬币。没有5美分的硬币，只有4个1美分的硬币。因此，它无法找到正确的找零方式。可以使用动态规划找到正确的找零方式（3个10美分和1个1美分）。

- AggieMan