递归变换算法

Question

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

例子:

• C(78, [1, 5, 10, 25, 50]) = 6

  • 我们可以从3x 25+ 3x 制作78 1,所以需要6个硬币

• C(48, [1, 7, 24, 42]) = 2

  • 48 = 2x 24,所以2个硬币就足够了

• C(35, [1, 3, 16, 30, 50]) = 3

  • 我们可以从2x 16+ 1x 制作35 3,所以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

这是变革问题.这是标准的递归解决方案,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]

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