algorithm - 零钱: Greedy Approach

Question

问题是让 n 美分随 25 美分、10 美分、5 美分和 1 美分变化，并使用最少的硬币总数。在四种面额分别为 25 美分、10 美分、5 美分和 1 美分的特殊情况下，我们有 c1 = 25、c2 = 10、c3 = 5 和 c4 = 1。

如果我们只有 25 美分、10 美分和便士(没有五分硬币) 可以使用，贪心算法会用六枚硬币找零30 美分——四分之一零五便士——而我们本可以使用三枚硬币，即三角硬币。

给定一组面额，我们如何判断贪婪方法是否创造了最优解？

Answer 1

您要问的是如何确定给定的硬币系统是否规范来解决找零问题。如果贪心算法总是给出最优解，则系统是规范的。您可以通过有限的步骤确定包含 1 美分硬币的硬币系统是否规范。详细信息以及某些情况下更有效的算法，请参阅 http://arxiv.org/pdf/0809.0400.pdf .