1

我正在尝试实施硬币兑换问题，该问题指出

硬币兑换问题被描述为给定一个值 N，如果我们想用 N 美分找零，并且我们有无限供应 S = {S1, S2, . . . , Sm} 值钱的硬币，有多少种方法可以找零？硬币的顺序无关紧要。用贪心法确定所有可能改变 N 分的方法。例如，对于 N = 4 和 S = {1, 2, 3}，有四种解：{1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}。所以输出应该是 4。对于 N = 10 和 S = {2, 5, 3, 6}，有五种解决方案：{2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 2, 6}，{2, 3, 5} 和{5, 5}。所以输出应该是5。

注意：这不是原始的硬币更换问题，我们必须找到最佳解决方案（即最小硬币数量）

在我下面的 python 实现中，我使用了一个名为 $check$ 的列表名称。问题是程序在整个运行期间都使用相同的 $check$ 列表，因此我得到了错误的结果。它应该使用它的函数调用本地的 $check$ 列表。任何人都可以找到解决这个问题的方法吗..

# N
N = 10

# Set of Changes
s = [2, 3, 5, 6]

lst = []
check = [0, 0, 0, 0]

def Coin_Change_Count(C, check):       
    for k in range(len(s)):        
        i = len(s) - k - 1
        t = C - s[i]

        if (t >= 0):
            if (s[i] == 2):
                check[0] += 1
            elif (s[i] == 3):
                check[1] += 1
            elif (s[i] == 5):
                check[2] += 1
            elif (s[i] == 6):
                check[3] += 1

            if (t >= s[0]):
                Coin_Change_Count(t, check)

            if (t == 0):
                if (not (check in lst)):
                    lst.append(check)

Coin_Change_Count(N, check)
print(len(lst))
4

0 回答 0