为什么代码会给我错误的金额输出？（更改制作问题）

Question

我正在尝试解决硬币找零问题，在该问题中我们必须找到加起来达到特定数量的最少硬币数量。

这是我想出的解决方案：

import sys
denomination = [1,6,10]
amount = 12

def coin_change(amount,denomination):
    coins = 0
    ans = [0]*(amount+1)
    temp = sys.maxsize
    for i in range(len(ans)):
        for j in range(len(denomination)):
            if denomination[j] <= i:
                ans[i] = min(temp, ans[i-denomination[j]]) + 1
    return ans

print(coin_change(amount,denomination))

输出为

[0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3].

为什么 12 的输出中最后一个数字是 3？我已经检查了很多次代码，但我仍然不明白为什么会这样。它为 6 的数量给出 1，因此它应该为 12 的数量而不是 3 给出 2。

我的代码有什么问题？

Answer 1

问题是 min(temp, ...) 是一个无用的调用，因为您永远不会减少 temp 的值。这个表达式总是转到 return 第二个参数。显然你真的需要比较备选方案并选择最佳的，所以这是错误的。

这就是你得到 3 的原因。最后尝试的面额是 10（当 j 是 2 时）。在那次尝试之前，ans[12] 实际上是 2，但它被 3 (10+1+1) 覆盖了！

这里更正：

import sys
denomination = [1,6,10]
amount = 12

def coin_change(amount,denomination):
    ans = [sys.maxsize]*(amount+1)  # initialise with maximum value
    for i in range(len(ans)):
        for j in range(len(denomination)):
            if denomination[j] <= i:
                if denomination[j] == i:
                    ans[i] = 1  # base case
                else:  # see if we can improve what we have
                    ans[i] = min(ans[i], ans[i-denomination[j]] + 1)
    return ans

print(coin_change(amount,denomination))

为什么代码会给我错误的金额输出？（更改制作问题）

Why does the code give me wrong output for an amount? (Change making problem)

python

dynamic-programming

为什么代码会给我错误的金额输出？ （更改制作问题）

Why does the code give me wrong output for an amount? (Change making problem)

python

dynamic-programming

为什么代码会给我错误的金额输出？（更改制作问题）