问题是使用硬币，硬币，硬币和硬币改变n美分，并使用最少的硬币总数 . 在四种面额是四分之一，硬币，镍币和硬币的特定情况下，我们有c1 = 25，c2 = 10，c3 = 5，c4 = 1 .
如果我们有 only quarters, dimes, and pennies (and no nickels) 使用，贪婪的算法将改变 30 cents using six coins -a四分之一和五便士 - 而我们可以使用 three coins ，即三角钱 .
给定一组面额，我们怎么能说贪婪方法是否能创造出最优解？
1 回答
你问的是如何决定一个给定的硬币系统是否为变化问题 . 如果贪婪算法总是提供最优解，则系统是规范的 . 您可以通过有限数量的步骤来确定包含1美分的硬币系统是否规范 . 在某些情况下，可以在http://arxiv.org/pdf/0809.0400.pdf中找到详细信息和更有效的算法 .