在动态编程硬币示例中使用无穷大 - 为什么这不会失败？

Question

一直在尝试了解如何在此页面上使用动态规划

https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

给定 N 个硬币的列表，它们的值（V1，V2，...，VN）和总和 S。找到总和为 S 的最小硬币数量（我们可以使用尽可能多的硬币我们想要的一种类型），或者报告说不可能 select 硬币总和为 S.

给定价值 1、3 和 5 的硬币。和 S 设置为 11.

Set Min[i] equal to Infinity for all of i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
   If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1

Output Min[S]

我很困惑为什么我们要为所有 i 设置无穷大。

更令人困惑的是总和为 1

If (Vj<=i AND Min[i-Vj]+1<Min[i])

Min[1] 不会未定义吗？代码不会在这里失败吗？他们为什么要添加 +1？

还是会继续下去，因为它是无限的？他们为什么在这里使用无限？什么是 N-1 他们从哪里得到的？

总的来说，我发现他们的解释很难理解。

Answer 1

希望这是直接翻译：

def dp_coin(S, coins):
    # set all values to infinity in range S/sum needed
    mn = [float("inf") for j in range(S+1)]
    # takes 0 coins to sum 0
    mn[0] = 0
    # start at second index 1
    for i in range(1, S+1):
        for j in range(len(coins)):
            if coins[j] <= i and mn[i-coins[j]]+1 < mn[i]:
                mn[i] = mn[i-coins[j]] + 1
    return mn[-1]

print(dp_coin(11, [1, 3, 5]))
3

如果你打印 mn 你会看到：

[0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 3]

与table相同：

Sum Min. nr. of coins   Coin value added to a smaller sum to
obtain this sum (it is displayed in brackets)
0   0   -
1   1   1 (0)
2   2   1 (1)
3   1   3 (0)
4   2   1 (3)
5   1   5 (0)
6   2   3 (3)
7   3   1 (6)
8   2   3 (5)
9   3   1 (8)
10  2   5 (5)
11  3   1 (10)

S是指需要的总金额，coins[j]相当于Vj，N是指硬币。

可以删除内部循环并简单地迭代硬币：

def dp_coin(S, coins):
    mn = [float("inf") for j in range(S+1)]
    mn[0] = 0
    for i in range(1, S+1):
        for j in coins:
            if j <= i and mn[i-j]+1 < mn[i]:
                mn[i] = mn[i-j] + 1
    return mn[-1]

在动态编程硬币示例中使用无穷大 - 为什么这不会失败？

Using infinity in dynamic programming coins example - why does this not fail?

python

dynamic-programming