贪心算法换币算法的坏情况是什么？

Question

换币问题是用最少的硬币数来换硬币。

你能给出一套贪婪算法不能给出最优解的硬币面额吗？这个集合应该包含一个便士，这样每n就有一个解。

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变得更大

Answer 2

硬币： 1，5，8

金额： 10

贪婪解决方案： 8，1，1 (3枚硬币)

最优： 5，5 (2枚硬币)

要在@xenteros评论上进行扩展，请查看维基百科 (顺便说一下)。你可以找到一个例子)：

对于所谓的标准硬币系统，就像美国和其他许多国家所使用的那样，一个贪婪的算法--选择不大于剩余数量的最大面值的硬币--将产生最佳效果。但是，对于任意硬币系统，情况并非如此:如果硬币面额为1、3和4，则贪婪的算法将选择三个硬币(4, 1，1)，而最优解是两个硬币(3,3)。

Answer 3

当可用硬币的数量有限时，贪婪算法并不总是有效的。假设您在收银机中有以下内容：

• $50: 3钞票
• $10: 11钞票
• $5: 6钞票
• 1:9美钞
• 季度: 55枚硬币
• 迪姆斯: 47枚硬币
• 镍币:零
• 硬币:4枚硬币

一位顾客进来购买价值69美分的糖果，用一张1美元的钞票付款，并需要得到31美分的零钱。

贪婪的算法将首先选择一个季度，然后需要多挑6美分。没有硬币，也只有4便士。因此，它将找不到正确的变化。使用动态规划可以找到正确的变化(3美分和1美分)。