Skip to main content
 首页 » 编程设计

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

2024年10月25日16三少

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

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

给定 N 个硬币的列表,它们的值 (V1, V2, … , VN) 和总和 S。找到总和为 S 的最小硬币数量(我们可以使用一种类型的硬币如我们所愿),或者报告不可能以总和为 S 的方式选择代币。

给定值(value) 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 他们从哪里得到的?

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

请您参考如下方法:

希望这是直接翻译:

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] 

与表格相同:

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]