贪心算法和硬币算法？

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

我知道这不是解决欧拉问题的正确方式，但我想要理解并学习如何最优地使用该算法。我的问题是，这是否被认为是一种合适的贪心算法？如果不是，我做错了什么。如果正确，我能否进行优化？

- tijko

---

贪心算法总是选择不超过仍须支付金额的最大面额硬币。 - Joran Beasley

这与您的主要问题不相关，但是代码 dict.update({key:value}) 对我来说似乎非常奇怪（因此我想知道是否有什么微妙的事情发生了）。但是，它与更清晰的 dict[key]=value 在效果上完全相同，我建议使用后者。当您需要添加许多值或另一个字典（例如 dict.update(dict2)）时，dict.update() 方法非常有用。 - Blckknght

@Blckknght 我原本认为没有办法使用 dict[key] = value 而不覆盖现有的值。 - tijko

dict[key]=value 会覆盖字典中已有的 key 对应的值，但不会删除字典中其他的值。 - Matt

@Blckknght，这是关于我想要在数据结构中的展示方式的问题。我本来想要一个 **{25:1,1,3}**，但是我需要将这些值放入另一个字典或列表中，对吗？我认为使用字典可能更好，或者像Joran的函数中那样将面额单独返回到一个列表中。 - tijko

Answer 1

贪心硬币算法可以计算给定金额的最佳找零方式。它适用于我们的硬币面额，但可能会在虚构的硬币面额（例如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
...

至少我是这样认为的，我可能是错的..（实际上我认为我是错的）

- Joran Beasley

---

我不确定所有的内容是否都正确，但是接下来我要处理递归部分，所以那一部分非常有帮助。我想先确保我用贪心算法做的事情是正确的，因为我把它作为一个更简单的练习从那个问题中分支出来了。 - tijko

这可能也会有所帮助：https://dev59.com/8G445IYBdhLWcg3w6ebz - Joran Beasley

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美分。

我会留给您编写代码。 正如您所说，这与 Euler 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]]

这有帮助吗？

- user448810

---

我的代码有什么让你不确定该如何称呼它的地方？ - tijko

Answer 3

Euler 76要求你计算一个数字的分区。这不是硬币问题，也不是贪心算法。计算数字分区的方法归功于欧拉（惊喜！），你可以在大多数算法或数学文本书中查找，或者在Google上搜索。你的程序应该几乎瞬间执行。

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

我在我的博客上两次讨论了分区问题，一次是当我计算分区数量时，另一次是当我枚举所有分区时。

- user448810

---

我知道这不是解决那个特定问题的方法。我想确保我的思路和代码在硬币问题和贪心算法方面是正确的。我编辑了我的帖子，明确说明了这一点。接下来，我将研究一种更优化的方法来解决欧拉76问题，所以你提到的其余部分应该会有所帮助。 - tijko

我会提供一个单独的答案，而不是在评论中回复。 - user448810