6

我一直在研究 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

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

4

3 回答 3

4

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

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

于 2012-07-27T21:18:52.773 回答
2

您已经编辑了您的问题，以询问使用给定的一组硬币对给定金额进行找零的最佳方式是什么；至少，我认为这是你要问的问题。我假设每种面额的硬币都有无限数量的可用硬币，或者至少足以让您可以随意使用每种面额的硬币。

让我们以使用 1 美分、5 美分、10 美分和 25 美分硬币兑换 1 美元的问题为例；一美元是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]]

这有帮助吗？

于 2012-07-28T00:00:39.297 回答
1

Euler 76 要求您计算一个数的分区。这不是硬币问题，也不是贪心算法。计算数字分区的方法归功于 Euler（惊喜！），您可以在大多数算法或数学课本或 Google 上查找它。您的程序应该几乎立即执行。

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

我在博客上讨论过分区两次，一次是计算分区数，另一次是枚举所有分区。

于 2012-07-27T23:35:57.557 回答