问题是用25美分、10美分、5美分和1美分的硬币组合成n美分，且使用最少数量的硬币。特别地，如果只有25美分、10美分和1美分的硬币（没有5美分硬币）可用，则贪心算法会用6枚硬币找零30美分——一个25美分和五个1美分，而我们本可以只用3枚硬币，即三个10美分。
给定一组面额，如何判断贪心方法是否创建了最优解？
给定一组面额，如何判断贪心方法是否创建了最优解？
硬币找零问题：贪心算法
6
- bhavya
6
你是在问如何解决这个问题吗？这个问题有一个简单的动态规划解决方案。 - Ami Tavory
@AmiTavory，我正在阅读Rosen的《离散数学及其应用》一书，他在书中引用了这个例子。我也认为这个问题类似于背包问题，并对贪心算法的解决方案感到惊讶。 - bhavya
抱歉，但我（至少）不明白你具体在问什么。也许你可以稍微编辑一下你的问题。 - Ami Tavory
@AmiTavory 他正在询问一个充分条件，如果给定，则贪心算法对于硬币找零问题是最优的。 - amit
啊，"贪心算法是否适用于这个问题"这句话让我有点困惑。不知道为什么无法编辑问题（也许是其他人（包括你？）正在编辑）。 - Ami Tavory
@bhavya 在这里看一下：[http://en.wikipedia.org/wiki/Change-making_problem#cite_note-2] - Ami Tavory
1个回答
1
您所询问的是如何确定给定的硬币系统是否符合找零问题的规范化标准。如果贪心算法总是能够给出最优解，那么该系统就是规范化的。您可以在有限步骤内确定一个包含1美分硬币的硬币系统是否规范化。更多细节和某些情况下更有效的算法，请参见http://arxiv.org/pdf/0809.0400.pdf。
- Edward Doolittle
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接