<分区>
在以下贪婪算法的找零问题中，解决了以下问题:如何用最少数量的硬币赚取给定数量的钱？
算法:如果可能，使用最有值(value)的硬币。假设我们有无限数量的每个硬币集。
我的教授，写了 (4) 不是产生最优解，谁能说为什么？ (或者为什么其他不是反例？)
1- {1,2,5}
2- {1,4,7}
3-{1,5,10}
4-{1,7,10}
<分区>
在以下贪婪算法的找零问题中，解决了以下问题:如何用最少数量的硬币赚取给定数量的钱？
算法:如果可能，使用最有值(value)的硬币。假设我们有无限数量的每个硬币集。
我的教授，写了 (4) 不是产生最优解，谁能说为什么？ (或者为什么其他不是反例？)
1- {1,2,5}
2- {1,4,7}
3-{1,5,10}
4-{1,7,10}
最佳答案
在需要代表 14 的情况下，对第 4 组中的硬币应用贪心策略不会产生最佳结果:
很容易看出，如果存在一个硬币C这样值 k*C至少可以由 k+1 组成coins 如果你拿走任何面额更高的硬币，那么贪心算法就不会成功。
在你的最后一组中 C=7 , k=2 , kC=14 .如果你拿10制作14 ，你需要五个硬币，大于k .
关于c++ - 一些修改的改变问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28785740/