贪心算法和硬币算法？

Question

我一直致力于项目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
...

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