为什么贪婪的硬币更换algorithm不适用于某些硬币套装？
我知道如何贪婪algorithm的硬币更换问题（支付一定的金额尽可能less的硬币）的作品 – 它总是select最大的面额硬币不超过剩余的总和 – 它总是find正确的解决scheme具体的硬币套。
但是对于一些硬币组，有贪婪algorithm失败的总和。 例如，对于集合{1, 15, 25}和总和30，贪婪algorithm首先select25，剩余5，然后5个1，总共六个硬币。 但最小数量的硬币的解决scheme是select15次两次。
一组硬币必须满足什么条件才能使贪婪algorithmfind所有和数的最小解？
通过使用贪婪的方法，可以使用一组形成一个matroid（ https://en.wikipedia.org/wiki/Matroid ）来解决硬币转换问题。 简而言之，一个matroid是一个有序对M =（S，l），满足下列条件：
- S是一个有限的非空集
- l是S的子集的非空族，称为独立子集，如果B> 1且A是B的一个子集，则A→1
- 如果A-> l，B-> l和| A | 那么有一些元素x-> BA使得AU {x} – > l
在我们的硬币更换问题中，S是一组所有硬币的降序价值。我们需要通过S中的最小数量的硬币达到V值
在我们的例子中，l是一个包含所有子集的独立集合，对于每个子集都有以下结果：它们中的值的总和是<= V
如果我们的集合是一个拟阵，那么我们的答案是l中的最大集合A，其中不能进一步添加x
为了检验，我们看看matrix的性质是否保持在集合S = {25,15,1}，其中V = 30现在，在L中有两个子集：A = {25}和B = {15,15} | A | <| B |，那么存在一些元素x-> BA使得AU {x} – > l（根据3）所以，{25,15}应该属于l，但是它自从25 + 15> 30
所以，S不是一个matroid，因此贪婪的方法就不行。
如果用贪婪algorithm改变的硬币的数量对于所有数量是最佳的，则硬币系统是规范的。
本文提供了一个O（n ^ 3）algorithm来决定一个硬币系统是否是规范的，其中n是不同种类的硬币的数量。
对于一个非规范的硬币系统来说，有一个数量c ，贪婪algorithm产生次优数量的硬币; c被称为反例。 如果最小的反例比最大的单币大，则硬币系统是紧密的。
在任何情况下，如果没有硬币的价值在加到最低面值时比低于它的面值的两倍还要低，贪婪algorithm就可以工作。
即{1,2,3}的工作原理是因为[1,3]和[2,2]添加了相同的值，但{1,15,25}不起作用，因为（对于更改30）15 + 15> 25 +1
一个容易记住的情况是，任何一套硬币，如果他们按升序sorting，你有：
coin[0] = 1 coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]
那么使用这种硬币的贪婪algorithm将起作用。
根据您查询的范围，可能会有更多的最佳（所需硬币数量）分配。 一个例子是如果你正在考虑的范围（6..8），你有硬币<6,7,8>，而不是<1,2,4,8>。
在N +上完成的最有效的硬币分配与上述规则相同，给你硬币1，2，4，8 …; 这只是任何数字的二进制表示。 从某种意义上说，基础之间的对话本身就是一个贪婪的algorithm。
Max Rabkin在本次讨论中提供了≥2N不等式的certificate： http : //olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf
