贪婪算法和硬币算法？

Question

我一直在做一些关于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

我知道这不是解决欧拉问题的方法，但是，我想了解并学习使用此算法的最佳方法。我的问题是，这会被认为是一个合适的贪婪算法吗？如果不是我做错了什么。如果正确，我可以改进优化吗？

Answer 1

Euler 76要求您计算一个数的分区。这不是硬币问题，也不是贪婪算法。一个数的分割数的计算方法是由于欧拉（惊奇！）你可以在大多数算法或数学文本中查找，也可以在谷歌上查找。你的程序应该马上执行。

顺便说一下，Project Euler的答案比p（100）的正常计算值少1，因为它忽略了p（0）=1的约定。因此，在编写计算分区的函数之后，Euler 76的答案是P（100）-1。

我在我的博客上讨论过两次分区，计算分区数量时是once，枚举所有分区时是again。

Answer 2

你已经编辑了你的问题，问什么是用一组硬币来改变给定数量的最佳方法；至少，我认为这是你要问的问题。我假设每个面额的硬币都有无限的数量，或者至少足够你使用你喜欢的每个面额的硬币。

举个例子，用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]]

有帮助吗？

Answer 3

贪心硬币算法计算出对给定的到期金额进行更改的最佳方式。它适用于我们的硬币面额，但可能会因硬币面额的组合而失败（例如，一枚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
...

至少我是这么想的，我可能错了……（事实上我认为我错了）