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

有 nn 件物品，第 ii 件重量 wiw_i、价值 viv_i，背包容量为 WW。每件物品只能完整地选一次或不选，求最大总价值。

1. 为什么暴力是指数级

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

递归写成：

F(i,c)=max⁡(F(i−1,c), F(i−1,c−wi)+vi).F(i,c)=\max\bigl(F(i-1,c),\ F(i-1,c-w_i)+v_i\bigr).

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

2. 状态定义

令

dp[i][c]dp[i][c]

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

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

3. 状态转移

对第 ii 件物品：

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

因此

dp[i][c]={dp[i−1][c],c<wi,max⁡{dp[i−1][c],dp[i−1][c−wi]+vi},c≥wi.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]=0dp[0][c]=0，答案是 dp[n][W]dp[n][W]。

4. 为什么转移正确

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

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

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

5. 复杂度与伪多项式

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

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

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

6. 一维空间压缩

第 ii 行只依赖第 i−1i-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−wi]dp[c-w_i] 会被当前物品再次使用，算法就变成完全背包。

空间降为 O(W)O(W)。

7. 一个例子

容量 W=7W=7，物品为

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

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

8. 恢复选择方案

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

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

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

9. 常见变体

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

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

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

评论