为什么贪婪的硬币变化算法对一些硬币集不起作用？
我理解硬币兑换问题的贪婪算法（用尽可能少的硬币支付特定金额）是如何工作的——它总是选择面额最大但不超过剩余金额的硬币——并且它总是为特定的硬币组找到正确的解决方案。
但对于某些硬币集，贪婪算法会失败。例如，对于集合{1,15,25}和总和30，贪婪算法首先选择25，剩下5，然后选择5个1，总共6枚硬币。但是，对于最少数量的硬币，解决方案是选择15枚硬币两次。
一组硬币必须满足什么条件，才能让贪婪算法找到所有总数的最小解？
共有3个答案
如果贪心算法给出的变化硬币数量对于所有数量都是最优的，那么硬币系统就是标准的。
本文给出了一个O（n^3）算法来判定一个硬币系统是否是标准的，其中n是不同种类硬币的数量。
对于非标准硬币系统，存在一个数量c，贪心算法会产生次优数量的硬币c被称为反例。如果最小的反例大于最大的一枚硬币，那么硬币系统就是紧密的。
在任何情况下，如果没有任何硬币的价值（当加到最低面值时）低于面值的两倍，则贪婪算法是有效的。
i、 e.{1,2,3}起作用是因为[1,3]和[2,2]加在同一个值上，而{1,15,25}不起作用是因为（对于变更30）15
形成拟阵的集合(https://en.wikipedia.org/wiki/Matroid)可以用贪婪方法解决换币问题。简言之，拟阵是满足以下条件的有序对M=（S，l）：
- S是有限非空集
在我们的换币问题中，S是一组所有硬币的降序值，我们需要通过S中最小数量的硬币来获得V值
在我们的例子中，l是一个包含所有子集的独立集，这样每个子集都有以下内容：其中值的总和为
如果我们的集合是拟阵，那么我们的答案是l中的最大集合a，其中可以进一步添加no x
为了检查，我们看拟阵的性质在集合S={25,15,1}中是否成立，其中V=30，在l中有两个子集：A={25}和B={15,15}，因为| A|
所以，S不是一个拟阵，因此贪婪的方法对它不起作用。
-
首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。 我需要证明对于当
-
我试图解决换硬币的问题，你用尽可能少的硬币来换钱。我尝试使用贪婪的方法——我的算法对硬币数组进行排序，从最大的硬币开始，并尽可能多地使用它，然后再移动到下一个硬币，将剩余的硬币分开。 这对初始测试用例有效： 硬币=[1,2,5]，数量=11 但这次失败了： 硬币=[186,419,83,408]，金额=6249 我不确定它为什么会失败，我仍在努力掌握贪婪的方法。非常感谢您的反馈！
-
问题是用硬币、一角硬币、五分硬币和一便士来换零钱，并且使用最少的硬币总数。在四个面值分别是硬币、一角硬币、五分硬币和一便士的特殊情况下，我们有c1=25、c2=10、c3=5和c4=1。 如果我们只有四分之一硬币、一角硬币和一分硬币（没有五分镍币）可供使用，贪婪算法将使用六枚硬币——四分之一硬币和五便士——兑换30美分，而我们可以使用三枚硬币，即三个一角硬币。 给定一组面额，我们如何判断贪婪方法是
-
贪婪的变更算法是通过选择可用的最高面额硬币进行变更，直到达到它试图进行的变更量。令人惊讶的是，这种算法实际上是以最有效的方式改变美国和欧元硬币面额的！ 然而，贪婪的算法有时会在做出改变时失败。假设我们有面额[25,15,1]，并试图赚31美分。贪婪的算法会选择25,1,1,1,1,1,1 (7硬币），而31美分实际上可以制作成15,15,1（3枚硬币）。 我想知道的是，是否有一种方法可以让贪婪算法
-
以人民币的硬币为例，假设硬币数量足够多。要求将一定数额的钱兑换成硬币。要求兑换硬币数量最少。 思路说明： 这是用贪婪算法的典型应用。在本例中用python来实现，主要思想是将货币金额除以某硬币单位，然后去整数，即为该硬币的个数；余数则做为向下循环计算的货币金额。 这个算法的问题在于，得出来的结果不一定是最有结果。比如，硬币单位是[1,4,6],如果将8兑换成硬币，按照硬币数量最少原则，应该兑换成为
-
我见过很多硬币更换问题，这个问题很独特。我尝试使用DP和递归，但我无法解决它。 这就是问题所在： 假设给定一个价格，X，其中X是美分，我有5种有限面额的硬币，1,5,10,20,50。我有不同数量的1、5、10、20、50分硬币。我想用最大数量的硬币来确定价格X。我该怎么做？（假设X总是可以用手头的硬币制作） 例如，如果价格X=52，并且 我有三枚一分硬币 我有四枚五分硬币 我有8枚10美分的硬币