贪心算法和硬币算法？
我一直在做一些关于Project Euler的问题/练习，希望用python练习/学习一些优化算法和编程习惯用法。
我遇到了一个问题，要求找到所有唯一的组合，至少使用两个值来求和为100。在研究这个问题时，我遇到了一些人提到硬币问题和贪婪算法，这就是这个问题的内容。
我以前听说过贪婪算法，但从未理解或使用过它。我想我会试一试。我仍然不确定这是否是正确的方法。
def greedy(amount):
combos = {}
ways = {}
denominations = [1,5,10,25]
## work backwards? ##
denominations.reverse()
for i in denominations:
## check to see current denominations maximum use ##
v = amount / i
k = amount % i
## grab the remainder in a variable and use this in a while loop ##
ways.update({i:v})
## update dictionarys ##
combos.update({i:ways})
while k != 0:
for j in denominations:
if j <= k:
n = k/j
k = k % j
ways.update({j:n})
combos.update({i:ways})
ways = {}
return combos我知道这不是解决Euler问题的方法，但是，我想了解和学习使用这个算法的最佳方法。我的问题是，这会被认为是一个合适的贪婪算法吗？如果不是，我做错了什么。如果正确，我可以改进优化吗？
回答 3
Stack Overflow用户
发布于 2012-07-28 05:18:53
贪婪硬币算法计算出在给定的到期金额内进行更改的最佳方式。它适用于我们的硬币面额，但可能无法与硬币的面额组成(例如。一枚7美分硬币和一枚12美分硬币)
下面是它的一个递归实现
>>> def pickBest(coins,due):
... if due == 0: return []
... for c in coins:
... if c<= due: return [c] + pickBest(coins,due-c)
...
>>> coins = [1,5,10,25]
>>> coins = sorted(coins,reverse=True)
>>> coins
[25, 10, 5, 1]
>>> print pickBest(coins,88)
[25, 25, 25, 10, 1, 1, 1]然而，我认为这不会像你所说的那样对你有多大帮助
您可能希望将其视为递归问题。
100 = 99 + 1
100 = 98 + 2 (2 = 1 + 1)
100 = 98 + (1 + 1)
100 = 97 + 3 (3 = 1 + 2)
100 = 97 + 2+1 (recall 2 = 1+1)
100 = 97 + 1+1 + 1
...至少我是这么想的，我可能是错的.(事实上我认为我错了)
Stack Overflow用户
发布于 2012-07-28 08:00:39
您已经编辑了您的问题，询问使用给定的一套硬币对给定的金额进行更改的最佳方式是什么；至少，我认为这就是您要问的问题。我假设每种面值的硬币都有无限的数量，或者至少足够你可以使用任何你喜欢的面值的硬币。
让我们举个例子，用1美分、5美分、10美分和25美分的硬币把一美元换成零钱；一美元等于100美分。贪婪算法总是取尽可能大的硬币。因此，在第一步，最大的硬币小于或等于目标金额，因此在输出中添加一个25美分的硬币，并将目标减少到75美分。在第二步，最大的硬币小于或等于减少的目标，因此在输出中添加一个25美分的硬币，并将目标减少到50美分。在第三步，最大的硬币小于或等于减少的目标，因此在输出中添加一个25美分的硬币，并将目标减少到25美分。在第四步，最大的硬币小于或等于减少的目标，所以添加一个25美分的硬币并将目标减少到0美分。现在没有什么可做的了，所以输出是四个25美分的硬币。
由于这并不是很有趣，让我们再试一次，目标是47美分。第一步输出一枚25美分的硬币，并将目标减少到22美分。现在不再可能输出25美分的硬币，所以输出小于或等于减少的目标的最大硬币，这是10美分的硬币，并将目标减少到12美分。在第三步，小于或等于减少的目标的最大硬币是10美分，所以输出该硬币并将目标减少到2美分。接下来的两步将分别输出1美分硬币，并将目标减少到零。所以输出结果是一枚25美分硬币，两枚10美分硬币和两枚1美分硬币，总共47美分。
我将把从那里开始编写代码留给您。正如你所说，这与欧拉76无关。
响应第一条评论的更新，现在已经消失了。
我不知道该怎么称呼你的代码。我想贪婪这个词已经足够好了。下面是我如何做的，其中包括调试输出，这样您就可以看到中间步骤：
def greedy(amount, denoms):
result = []
while (amount > 0):
print amount, denoms, result
if (amount >= denoms[0]):
num = amount // denoms[0]
amount -= (num * denoms[0])
result.append([denoms[0], num])
denoms = denoms[1:]
return result
print greedy(100, [25,10,5,1])
print ""
print greedy(100, [10,5,1])
print ""
print greedy(100, [5,1])
print ""
print greedy(100, [1])
print ""
print greedy(47, [25,10,5,1])输出结果为：
100 [25, 10, 5, 1] []
[[25, 4]]
100 [10, 5, 1] []
[[10, 10]]
100 [5, 1] []
[[5, 20]]
100 [1] []
[[1, 100]]
47 [25, 10, 5, 1] []
22 [10, 5, 1] [[25, 1]]
2 [5, 1] [[25, 1], [10, 2]]
2 [1] [[25, 1], [10, 2]]
[[25, 1], [10, 2], [1, 2]]这有帮助吗？
Stack Overflow用户
发布于 2012-07-28 07:35:58
Euler 76要求您计算一个数字的分区。这不是硬币问题，也不是贪婪的算法。计算一个数的分区的方法是由于Euler (令人惊讶！)你可以在大多数算法、数学课本或者谷歌上查到它。您的程序应该几乎立即执行。
顺便说一句，Project Euler的答案比正常的P(100)计算少1，因为它忽略了P(0)=1的约定。因此，在您编写计算分区的函数后，Euler 76的答案是P(100)-1。
我已经在我的博客上讨论了两次分区，当我计算分区的数量时，once和当我枚举所有分区时，again。
https://stackoverflow.com/questions/11695655
复制相似问题
腾讯云开发者
