python - 贪心算法和硬币算法？

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

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

至少我是这么想的，我可能是错的..(事实上我认为我错了)