6

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

例子：

  • 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]
4

3 回答 3

19

这是改变的问题。这是标准的递归解决方案，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]

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

于 2012-09-20T20:29:56.733 回答
2

尝试使用贪心算法（最大的硬币优先）。应用到总数后从列表中删除硬币并从内部再次调用该函数。

于 2012-09-20T20:23:41.243 回答
0

所以寻找动态编程实现的最佳去处是：interactive 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
于 2017-05-12T12:17:08.190 回答