贪心换币算法的缺点是什么？
硬币更换问题是使用最少的硬币进行硬币更换。
你能给出一组硬币面额吗？对于这些硬币面额，贪婪算法不能给出最优解。集合中应包含一便士，以便每n有一个解决方案。
共有3个答案
当可用的硬币数量有限时，贪婪算法并不总是有效。假设你在收银机里有以下东西：
- 50美元：3张钞票
- 10美元： 11张钞票
- 5美元：6张钞票
- 1美元：9张钞票
- 四分之一：55硬币
- 一角硬币： 47硬币
- 镍：无
- 便士： 4枚硬币
一位顾客进来买了价值69美分的糖果，付了1美元，需要找31美分的零钱。
贪婪算法将首先选择一个25美分，然后再选择6美分。没有镍币，只有4便士。因此，它将无法找到正确的更改。使用动态规划可以找到正确的零钱（3美分和1便士）。
硬币： 1,5,8
数量： 10
贪婪的解决方案： 8,1,1（3硬币）
最佳： 5,5（2硬币）
要扩展@xentoros评论，请查看维基百科（btw。你会找到一个例子）：
对于所谓的标准硬币系统，就像美国和其他许多国家使用的那样，贪婪算法选择最大面额的硬币（不大于剩余的硬币数量），将产生最佳结果。但是，对于任意硬币系统，情况并非如此：如果硬币面额为1、3和4，那么为了得到6，贪婪算法将选择三枚硬币（4,1,1），而最佳解决方案是两枚硬币（3,3）。
好吧，给定10,7,1硬币变化15：
15 = 10 + 1 + 1 + 1 + 1 + 1 // greedy (6 coins)
15 = 7 + 7 + 1 // optimal (3 coins)
您可以很容易地生成一个效率尽可能低的贪婪解决方案：只需将可用硬币设置为1，N-1，N，然后尝试更改2*N-2：
N, 1, 1, ..., 1 // greedy (N - 1 coins)
N-1, N-1 // optimal (2 coins)
现在，使N变大
-
主要内容：贪心算法的实际应用《 算法是什么》一节讲到，算法规定了解决问题的具体步骤，即先做什么、再做什么、最后做什么。贪心算法是所有算法中最简单，最易实现的算法，该算法之所以“贪心”，是因为算法中的每一步都追求最优的解决方案。 举个例子，假设有 1、2、5、10 这 4 种面值的纸币，要求在不限制各种纸币使用数量的情况下，用尽可能少的纸币拼凑出的总面值为 18。贪心算法的解决方案如下： 率先选择一张面值为 10 的纸币，可以
-
首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。 我需要证明对于当
-
问题是用硬币、一角硬币、五分硬币和一便士来换零钱，并且使用最少的硬币总数。在四个面值分别是硬币、一角硬币、五分硬币和一便士的特殊情况下，我们有c1=25、c2=10、c3=5和c4=1。 如果我们只有四分之一硬币、一角硬币和一分硬币（没有五分镍币）可供使用，贪婪算法将使用六枚硬币——四分之一硬币和五便士——兑换30美分，而我们可以使用三枚硬币，即三个一角硬币。 给定一组面额，我们如何判断贪婪方法是
-
本文向大家介绍python 贪心算法的实现，包括了python 贪心算法的实现的使用技巧和注意事项，需要的朋友参考一下 贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不
-
以人民币的硬币为例，假设硬币数量足够多。要求将一定数额的钱兑换成硬币。要求兑换硬币数量最少。 思路说明： 这是用贪婪算法的典型应用。在本例中用python来实现，主要思想是将货币金额除以某硬币单位，然后去整数，即为该硬币的个数；余数则做为向下循环计算的货币金额。 这个算法的问题在于，得出来的结果不一定是最有结果。比如，硬币单位是[1,4,6],如果将8兑换成硬币，按照硬币数量最少原则，应该兑换成为
-
我试图用Python 3.x中的贪婪算法解决背包问题。下面是我的代码，以及我用来测试它的示例案例。每个示例案例的形式为行[0]=最大权重，行[1:]的形式为（权重，值。） 成功案例1： 上一次我在重写程序之前出现这样的错误，是在与int类型进行斗争。这一次似乎是在断绝关系，但我不确定如何修复它。非常感谢任何帮助。我只知道当我看到它的时候这会是一个简单的解决方案... 编辑：这必须与我的列表如何排序