我理解硬币改变问题的贪婪算法（用尽可能少的硬币支付特定金额）是如何工作的 - 它总是选择具有最大面额但不超过剩余总和的硬币 - 并且它总是找到正确的解决方案特定的硬币套装。
但是对于一些硬币集，有贪婪算法失败的总和。例如，对于集合{1, 15, 25}和总和30，贪婪算法首先选择25，剩余5，然后五个1，总共六个硬币。但硬币数量最少的解决方案是选择15两次。
一组硬币必须满足哪些条件才能使贪心算法找到所有金额的最小解？
形成拟阵（https://en.wikipedia.org/wiki/Matroid）的集合可以用于通过使用贪婪方法来解决硬币变化问题。简而言之，拟阵是有序对M =（S，l）满足以下条件：
在我们的硬币更换问题中，S是一组递减顺序值的所有硬币我们需要通过S中最小硬币数量来达到V值
在我们的例子中，l是一个独立的集合，包含所有子集，使得每个子集的以下成立：它们中的值的总和是<= V
如果我们的集合是一个matroid，那么我们的答案是l中的最大集合A，其中不能进一步添加x
为了检查，我们看看matroid的属性是否在集合S = {25,15,1}中保持，其中V = 30现在，l中有两个子集：A = {25}且B = {15,15} | A | <| B |，然后有一些元素x-> B-A使得A U {x} - > l（根据3）所以，{25,15}应该属于l，但是它自25 + 15> 30以来是一个矛盾
所以，S不是一个拟阵，因此贪婪的方法不适用于它。
在任何没有硬币的情况下，当加到最低面额时，它的值低于直接小于它的面额的两倍，贪婪算法起作用。
即{1,2,3}有效，因为[1,3]和[2,2]加上相同的值，但是{1,15,25}不起作用，因为（对于变化30）15 + 15> 25 +1
这是一个复发问题。给定一组硬币{Cn, Cn-1, . . ., 1}，这样对于1 <= k <= n, Ck > Ck-1，贪婪算法将产生最小数量的硬币，如果Ck> Ck-1 + Ck-2和值V=(Ck + Ck-1) - 1，将贪婪算法应用于硬币子集{Ck, Ck-1, . . ., 1}，其中Ck <= V导致的硬币数量少于将贪婪算法应用于硬币{Ck-1, Ck-2, . . ., 1}子集所导致的数量。
测试很简单：对于`1 <= k <= n，测试贪心算法为Ck + Ck-1 - 1的值产生的硬币数。对硬币集{Ck，Ck-1，...执行此操作。 。 。，1}和{Ck-1，Ck-2 ,. 。 。，1}。如果对于任何k，后者产生的硬币比前者少，则贪心算法将不适用于该硬币集。
例如，当n = 4时，考虑硬币集{C4，C3，C2,1} = {50,25,10,1}。以k = n = 4开始，然后V = Cn + Cn-1 -1 = 50 + 25-1 = 74作为测试值。对于V = 74，G {50,25,10,1} = 7个硬币。 G {25,10,1} = 8个硬币。到现在为止还挺好。现在让k = 3。然后V = 25 + 10-1 = 34。 G {25,10,1} = 10个硬币，但G {10,1} = 7个硬币。因此，我们知道贪婪算法不会最小化硬币组的硬币数量{50,25,10,1}。另一方面，如果我们在这个硬币组中添加一个镍币，则G {25,10,5,1} = 6且G {10,5,1} = 7.同样，对于V = 10 + 5-1 = 14，我们得到G {10,5,1} = 5，但G {5,1} = 6.所以，我们知道，Greedy适用于{50,25,10,5,1}。
这引出了一个问题：什么应该是硬币的面额，满足贪婪算法，这导致从1到100的任何值的最小的最坏情况数量的硬币？答案非常简单：100个硬币，每个硬币具有1到100的不同值。可以说这不是很有用，因为它可以在每次交易时线性搜索硬币。更不用说铸造这么多不同面额并跟踪它们的费用。
现在，如果我们想要主要最小化面额数量，同时最小化由Greedy生产的1到100之间的任何值的硬币结果数量，那么硬币的面额为2：{64,32,16,8,4 ，2,1}导致任何值1：100最多6个硬币（7位数的最大值1，其值小于十进制100）。但这需要7种面额的硬币。五种面额{50,25,10,5,1}的最坏情况是8，其发生在V = 94和V = 99。权力为3 {1,3,9,27,81}的硬币也只需要5个面额可供贪婪服务，但也会产生8个硬币的最差情况，值为62和80.最后，使用任何五个面额{64,32,16,8,4,2,1}的子集不能排除'1'，并且满足贪婪，也将导致最多8个硬币。所以有一个线性的权衡。将面额数从5增加到7会减少分别代表1到100之间的任何值所需的最大硬币数量，从8到6。
另一方面，如果你想最大限度地减少买家和卖家之间交换的硬币数量，假设每个硬币在口袋里至少有一个硬币，那么这个问题相当于平衡任何硬币所需的最少重量。重量从1到N磅。事实证明，如果硬币面额以3：{1, 3, 9, 27, . . .}的幂给出，则在购买中交换的硬币数量最少。
如果由贪婪算法改变的硬币数量对于所有量是最佳的，则硬币系统是规范的。
对于非规范硬币系统，有一个量的c，贪婪算法产生次优数量的硬币; c被称为反例。如果最小的反例大于最大的单个硬币，则硬币系统是紧的。
一个容易记住的案例是任何一组硬币，如果它们按升序排序，你有：
coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]
然后使用这种硬币的贪婪算法将起作用。
根据您查询的范围，可能会有更优化（根据所需的硬币数量）分配。这方面的一个例子是，如果你正在考虑范围（6..8），你有硬币<6,7,8>而不是<1,2,4,8>。
在N +上完成的最有效的硬币分配与上述规则相同，为您提供硬币1,2,4,8 ......;它只是任何数字的二进制表示。从某种意义上说，基地之间的对话本身就是一种贪婪的算法。
Max Rabkin在本次讨论中提供了关于> = 2N不等式的证明：http://olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf