algorithm - 为什么贪心找零算法对某些币组不起作用？

Question

我理解硬币找零问题的贪心算法(用尽可能少的硬币数支付特定金额)是如何工作的——它总是选择面额最大的硬币，不超过剩余的总和——而且它总是找到特定硬币组的正确解决方案。

但对于某些硬币组，存在贪婪算法失败的总和。例如对于集合{1, 15, 25} 和30，贪心算法先选择25，余数为5，再选择5个1，共6个硬币。但是硬币数量最少的解决方案是两次选择15。

一组硬币必须满足什么条件才能使贪心算法找到所有总和的最小解？

Answer 1

形成拟阵 (https://en.wikipedia.org/wiki/Matroid) 的集合可用于通过贪心法解决换硬币问题。简而言之，拟阵是有序对 M = (S,l) 满足以下条件:

1. S是有限非空集
2. l 是 S 的非空子集族，称为独立子集，如果 B->l 并且 A 是 B 的子集，则 A -> l
3. 如果 A-> l，B-> l 和 |A| < |B|，则存在某个元素 x-> B-A 使得 A U {x} ->l

在我们换硬币的问题中，S 是一组按值(value)递减顺序排列的所有硬币 我们需要通过 S 中最少数量的硬币来实现 V 的值(value)

在我们的例子中，l 是一个包含所有子集的独立集合，使得每个子集都满足以下条件:它们中值的总和是 <=V

如果我们的集合是一个拟阵，那么我们的答案就是l中的最大集合A，其中不能进一步添加x

为了检查，我们查看拟阵的属性是否在集合 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 不是拟阵，因此贪心法对它不起作用。