递归变更生成算法

Question

给定目标金额和硬币面额列表，我的代码应该找到达到目标金额所需的最少硬币。

示例：

>

C（78，[1, 5, 10, 25, 50]）=6

• 我们可以从3x253x1做78，所以需要6个硬币

C（48[1,7,24,42]）=2

• 48=2x24，因此2枚硬币就足够了

C（35[1,3,16,30,50]）=3

• 我们可以从2x161x3中得到35，所以3个硬币就足够了

我用for循环编写了代码，但如何使其递归？

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]

Answer 1

因此，寻找动态编程实现的最佳场所是：交互式python

然而，经过一点测试，我发现它不是最快的解决方案。它的好处是，一次运行就足以找到所有更改值的值。

我最喜欢的还是在缓存中使用递归：

from collections import defaultdict
from functools import lru_cache


@lru_cache(maxsize=1024)
def greedy(coin_list, change):
    if change in coin_list:
        return defaultdict(int, [(change, 1)])
    else:
        min_coins = change
        for c in [coin for coin in coin_list if coin < change]:
            result_min1 = greedy(coin_list, change - c)
            num_coins = 1 + sum(result_min1.values())
            if num_coins <= min_coins:
                min_coins = num_coins
                result = defaultdict(int, [(c, 1)])
                for c1, n in result_min1.items():
                    result[c1] += n
        return result

Answer 2

尝试使用贪婪算法（首先是最大的硬币）。将硬币从列表中移除，然后应用总数，并从内部再次调用该函数。

Answer 3

这是变革的问题。下面是标准的递归解决方案，V是硬币列表，C是目标金额：

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

这是一个优化版本，使用动态编程：

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

这两种实现都将始终返回最佳解决方案，但对于大输入，第二种实现将更快。请注意，其他答案中建议的贪婪算法仅对某些货币组合给出了最优解，例如，它适用于美国硬币。