0-1 背包问题动态规划解法：5 个物品示例及详细分析

用动态规划算法解决 0-1 背包问题：五个物品示例及详细分析

问题描述：

有 5 个物品，重量分别为：(w1, w2, w3, w4, w5) = (4, 6, 3, 5, 2)，价值分别为：(v1, v2, v3, v4, v5) = (6, 3, 8, 10, 12)，背包总重量不能超过 12。请画出 c[i,w] 二维数组，并给数组每个元素填上应有的数值，最终求得 c[5,12]，即最大能装多少价值的物品，并且回答出对应哪些物品放入背包，哪些物品没有放入背包。

解题思路：

c[i,w] 表示前 i 个物品，在背包容量为 w 的情况下，能够装下的最大价值。

根据动态规划的思想，我们可以分解成子问题来求解，先考虑只有一个物品的情况：

c[1,w] = 0, if w < w1
c[1,w] = v1, if w >= w1

再考虑有两个物品的情况：

c[2,w] = c[1,w], if w < w2
c[2,w] = max{c[1,w], c[1,w-w2]+v2}, if w >= w2

类似地，我们可以得到 c[3,w]、c[4,w]、c[5,w] 的表达式：

c[3,w] = max{c[2,w], c[2,w-w3]+v3}
c[4,w] = max{c[3,w], c[3,w-w4]+v4}
c[5,w] = max{c[4,w], c[4,w-w5]+v5}

根据以上公式，我们可以填写出 c[i,w] 的二维数组：

 0  1  2  3  4  5  6  7  8  9 10 11 12

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 6 6 6 6 6 6 6 6 6 2 0 0 0 0 6 6 8 8 8 8 8 8 9 3 0 0 0 8 8 8 8 14 14 14 16 16 16 4 0 0 0 8 8 10 10 14 14 18 18 20 22 5 0 12 12 12 12 14 14 18 20 22 24 24 26

因此，最大能装多少价值的物品为 c[5,12]=26，对应的物品放入背包的情况如下：

第5个物品 (价值 12，重量 2) 放入背包
第4个物品 (价值 10，重量 5) 放入背包
第3个物品 (价值 8，重量 3) 放入背包
第2个物品 (价值 3，重量 6) 没有放入背包
第1个物品 (价值 6，重量 4) 没有放入背包

代码实现：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

weights = [4, 6, 3, 5, 2]
values = [6, 3, 8, 10, 12]
capacity = 12

max_value = knapsack(weights, values, capacity)
print(f"最大价值：{max_value}")

总结：

动态规划算法在解决 0-1 背包问题时，通过将问题分解成子问题，并利用子问题的解来求解原问题，最终得到最优解。该算法高效且易于理解，适用于各种背包问题场景。