0-1 背包与动态规划入门

有 $n$ 件物品，第 $i$ 件重量 $w_i$、价值 $v_i$，背包容量为 $W$。每件物品只能完整地选一次或不选，求最大总价值。

1. 为什么暴力是指数级

每件物品有“选/不选”两种决策，共有 $2^n$ 个子集。逐个检查得到 $O(2^n)$ 算法。

递归写成：

$$F(i,c)=\max\bigl(F(i-1,c),\ F(i-1,c-w_i)+v_i\bigr).$$

朴素递归会反复计算相同的 $(i,c)$，这正是动态规划要消除的重叠子问题。

2. 状态定义

令

$$dp[i][c]$$

表示只考虑前 $i$ 件物品、容量不超过 $c$ 时的最大价值。

状态必须包含“已经处理到哪件物品”，否则无法保证每件只使用一次。

3. 状态转移

对第 $i$ 件物品：

• 不选：价值是 $dp[i-1][c]$；
• 选：需要 $c\ge w_i$，价值是 $dp[i-1][c-w_i]+v_i$。

因此

$$dp[i][c]= \begin{cases} dp[i-1][c],&c<w_i,\\ \max\{dp[i-1][c],dp[i-1][c-w_i]+v_i\},&c\ge w_i. \end{cases}$$

边界为 $dp[0][c]=0$，答案是 $dp[n][W]$。

4. 为什么转移正确

任意最优方案对第 $i$ 件物品只有两种情况：

• 不含它，则剩余方案一定是前 $i-1$ 件、容量 $c$ 下的最优解；
• 含它，去掉它后一定是前 $i-1$ 件、容量 $c-w_i$ 下的最优解。

若剩余部分不是最优，就能替换成更优子方案并改进原方案，矛盾。这就是最优子结构。

5. 复杂度与伪多项式

状态数为 $n(W+1)$，每个状态 $O(1)$ 转移：

$$T=O(nW),\qquad S=O(nW).$$

这不是关于输入位数的真正多项式时间。容量 $W$ 用二进制表示只需 $\Theta(\log W)$ 位，而算法依赖数值 $W$，所以称为伪多项式算法。

6. 一维空间压缩

第 $i$ 行只依赖第 $i-1$ 行，可压缩为：

dp[0..W] = 0
for each item i:
    for c = W down to w[i]:
        dp[c] = max(dp[c], dp[c - w[i]] + v[i])

容量必须从大到小枚举。若从小到大，刚更新的 $dp[c-w_i]$ 会被当前物品再次使用，算法就变成完全背包。

空间降为 $O(W)$。

7. 一个例子

容量 $W=7$，物品为

$$(w,v)=(1,1),(3,4),(4,5),(5,7).$$

最优方案选择重量 3 和 4 的物品，总重量 7、总价值 9。虽然重量 5 的物品单件价值最高，但选它后剩余容量无法组成更优方案，这说明局部贪心不可靠。

8. 恢复选择方案

保留二维表时，从 $(n,W)$ 反向判断：

• 若 $dp[i][c]=dp[i-1][c]$，第 $i$ 件可不选；
• 否则选了第 $i$ 件，记录它并令 $c\leftarrow c-w_i$。

若存在相等的两种最优转移，方案可能不唯一。需要字典序或物品数等次级目标时，要把规则写进状态或回溯策略。

9. 常见变体

• 完全背包：每件可无限次，容量从小到大枚举；
• 多重背包：每件有数量上限，可二进制拆分；
• 恰好装满：除 $dp[0]=0$ 外初始化为 $-\infty$；
• 价值维 DP：当价值和较小而容量很大时，求达到某价值的最小重量；
• 二维费用：状态加入第二个容量维度。

10. 0-1 与分数背包的分界

分数背包允许切分物品，按单位重量价值贪心正确；0-1 背包不允许切分，容量离散效应会破坏交换论证，因此需要动态规划或其他组合优化方法。