c++ - 一些修改带来的改变问题

Question

在以下贪心算法的找零问题中，解决以下问题：如何用最少数量的硬币赚到给定数量的钱？

算法：尽可能使用最有价值的硬币。假设我们有无限数量的每组硬币。

我的教授，写的（4）没有产生最佳解决方案，任何人都可以说为什么？（或者为什么其他不是反例？）

1- {1,2,5}

2- {1,4,7}

3-{1,5,10}

4-{1,7,10}

Answer 1

在需要表示 14 的情况下，对第 4 组的硬币应用贪心策略不会产生最佳结果：

• 贪婪策略将尽快获得 10，以 4 便士结束，总共 5 个硬币
• 最佳策略是采取两个七，总共两个硬币。

很容易看出，如果存在一个硬币，如果你拿走任何一个面值更高的硬币，那么C它的价值k*C至少可以由硬币组成k+1，那么贪心算法就不会成功。

在你的最后一组C=7, k=2, kC=14. 如果你拿来10做14，你需要五个硬币，大于k。