背包问题 (Knapsack Problem)

背包问题是动态规划中最经典的模型。

0/1 背包问题

问题描述： 有一个背包，容量为 \(W\)。有 \(N\) 种物品，每种物品只有一件。第 \(i\) 件物品的重量是 \(wt[i]\)，价值是 \(val[i]\)。求解将哪些物品装入背包可使价值总和最大。

特点：每种物品要么选 (1)，要么不选 (0)。

状态定义

dp[i][w] 表示：对于前 \(i\) 个物品，在背包容量为 \(w\) 时能拿到的最大价值。

转移方程

对于第 \(i\) 个物品：

1. 不装: dp[i][w] = dp[i-1][w] (继承前 \(i-1\) 个的结果)
2. 装: dp[i][w] = dp[i-1][w - wt[i]] + val[i] (前提是能装下，即 \(w \ge wt[i]\))

取两者的最大值。

二维数组版本

def knapsack_01(W, wt, val, n):
    # dp[i][j] 大小为 (n+1) x (W+1)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if w - wt[i-1] < 0:
                # 装不下，只能不选
                dp[i][w] = dp[i-1][w]
            else:
                # 选 或 不选，取最大值
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - wt[i-1]] + val[i-1]
                )
    return dp[n][W]

一维数组优化 (空间压缩)

因为 dp[i] 只依赖于 dp[i-1]，我们可以把状态压缩成一行。 注意：为了防止使用本层计算过的新结果覆盖上一层的数据，内层循环需要倒序遍历。

def knapsack_01_optimized(W, wt, val, n):
    dp = [0] * (W + 1)

    for i in range(n):
        # 必须倒序遍历！
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

    return dp[W]

# 测试
W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
print(knapsack_01_optimized(W, wt, val, 3)) # 6 (选物品 0 和 1)

完全背包问题

问题描述： 与 0/1 背包类似，但每种物品有无限件可用。

解法： 唯一的区别在于一维数组优化时的遍历顺序。

• 0/1 背包：倒序遍历 (保证每个物品只拿一次)。
• 完全背包：正序遍历 (允许一个物品被多次放入)。

def knapsack_complete(W, wt, val, n):
    dp = [0] * (W + 1)

    for i in range(n):
        # 正序遍历
        for w in range(wt[i], W + 1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

    return dp[W]

本章小结

问题类型	特点	遍历顺序 (一维数组)
0/1 背包	每个物品限 1 个	外层遍历物品，内层倒序遍历容量
完全背包	每个物品无限个	外层遍历物品，内层正序遍历容量

这是各类背包变体（如多重背包、分组背包）的基础。

---

下一章：贪心算法