硬币更换：贪婪的方法
问题是用硬币、一角硬币、五分硬币和一便士来换零钱，并且使用最少的硬币总数。在四个面值分别是硬币、一角硬币、五分硬币和一便士的特殊情况下，我们有c1=25、c2=10、c3=5和c4=1。
如果我们只有四分之一硬币、一角硬币和一分硬币（没有五分镍币）可供使用，贪婪算法将使用六枚硬币——四分之一硬币和五便士——兑换30美分，而我们可以使用三枚硬币，即三个一角硬币。
给定一组面额，我们如何判断贪婪方法是否创造了最优解？
共有1个答案
你要问的是如何决定一个给定的硬币系统对于变革问题是否规范。如果贪婪算法总是给出最优解，系统就是规范的。你可以在有限的步骤中决定一个包含1美分硬币的硬币系统是否规范。详细信息，以及在某些情况下更有效的算法，可以在http://arxiv.org/pdf/0809.0400.pdf.中找到
-
我试图在硬币兑换问题中实现贪婪方法，但需要降低时间复杂度，因为编译器不会接受我的代码，而且由于我无法验证，我甚至不知道我的代码是否正确。函数应返回进行更改所需的注释总数。如果无法获得给定金额的更改，则返回-1。如果金额等于面额列表中可用的货币之一，则返回1。
-
首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。 我需要证明对于当
-
以人民币的硬币为例，假设硬币数量足够多。要求将一定数额的钱兑换成硬币。要求兑换硬币数量最少。 思路说明： 这是用贪婪算法的典型应用。在本例中用python来实现，主要思想是将货币金额除以某硬币单位，然后去整数，即为该硬币的个数；余数则做为向下循环计算的货币金额。 这个算法的问题在于，得出来的结果不一定是最有结果。比如，硬币单位是[1,4,6],如果将8兑换成硬币，按照硬币数量最少原则，应该兑换成为
-
我正在尝试实现一个小的贪婪算法，在这个算法中，用户输入一定数量的钱（例如：9.25），我们输出的硬币数量最少，我们可以兑换（25美分、10美分、5美分和1美分）。 该算法适用于整数金额，如10或20，以及只需要程序使用25美分硬币的金额。 如果我尝试9.10或9.01这样的数值，就会得到一个运行时错误，即有符号整数溢出。我明白这意味着什么，但我不明白硬币的价值怎么会突然这么高。
-
我理解硬币兑换问题的贪婪算法（用尽可能少的硬币支付特定金额）是如何工作的——它总是选择面额最大但不超过剩余金额的硬币——并且它总是为特定的硬币组找到正确的解决方案。 但对于某些硬币集，贪婪算法会失败。例如，对于集合和总和30，贪婪算法首先选择25，剩下5，然后选择5个1，总共6枚硬币。但是，对于最少数量的硬币，解决方案是选择15枚硬币两次。 一组硬币必须满足什么条件，才能让贪婪算法找到所有总数的最
-
贪婪的变更算法是通过选择可用的最高面额硬币进行变更，直到达到它试图进行的变更量。令人惊讶的是，这种算法实际上是以最有效的方式改变美国和欧元硬币面额的！ 然而，贪婪的算法有时会在做出改变时失败。假设我们有面额[25,15,1]，并试图赚31美分。贪婪的算法会选择25,1,1,1,1,1,1 (7硬币），而31美分实际上可以制作成15,15,1（3枚硬币）。 我想知道的是，是否有一种方法可以让贪婪算法