要赚 6.39 美元，您可以选择：
- 5 美元的钞票
- 1 美元的钞票赚 6 美元。
- 25 美分硬币，赚 6.25 美元
- 10 美分硬币，赚 6.35 美元
- 四个 1 美分硬币，赚 6.39 美元。
但是，如果货币有权重为 1,7 和 10 的硬币，则它不起作用。我的问题是，为什么贪心算法仅对少数权重有效？给定权重集满足贪心算法并同时达到最优的条件是什么？
问问题
850 次
2 回答
2
David Pearson 在“变革问题的多项式时间算法”中研究了这个确切的问题。
不幸的是，它没有提供一个优雅的数学属性来回答这个问题。它基于这样一个事实，即如果贪心算法不起作用，则反例将出现在有限数量的值中，并且这些值具有使得检查每个值变得便宜的属性。
于 2013-07-08T15:02:06.317 回答
0
一些答案可以在这篇文章中找到：http: //arxiv.org/pdf/0801.0120v2.pdf
（至少根据他们的摘要，我没有阅读整篇论文）
于 2013-07-08T08:41:08.327 回答