3.7 0/1背包算法

这一篇讲动态规划最经典、最常考的应用——0/1 背包。它是 DP 思想的完美载体：状态定义、转移方程、空间优化都齐全，而且它还是理解第八卷 NP 完全性（8.6 子集和）和第九卷近似算法（9.4 PTAS）的入口。

1.问题：容量有限，怎么装价值最大

你有 $n$ 个物品，每个物品有重量 $w_i$ 和价值 $v_i$ 。背包容量 $W$ 。每个物品要么拿、要么不拿（0/1，不能拆分），目标是让拿的物品总重量 $\le W$ 、且总价值最大。

"0/1"是关键——每个物品只有"拿(1)/不拿(0)"两种选择，不能拿半个。如果可以拆分（拿 $0.3$ 个），那是分数背包，能用贪心（按单位重量价值降序拿），但 0/1 背包贪心失效，必须 DP。

2.为什么贪心失效

直觉的贪心是"按单位价值 $v_i/w_i$ 降序拿"。但这会错：比如容量 50，物品 A(重40值40，单位1)、B(重20值30，单位1.5)、C(重30值30，单位1)。贪心按单位价值先拿 B（最划算），剩 30，再拿 C 刚好满，总价值 60。但最优是拿 A+C，总价值 70。

贪心错在哪？"先把单位价值最高的拿掉"这个选择不是全局最优的一部分——可能为了拿那个单位价值高的，占掉了本该放更重但总价值更高组合的空间。贪心选择性质不成立，得 DP 穷举每个物品的拿/不拿。

4.填表与空间优化

按 $i=1,\dots,n$ 、 $c=0,\dots,W$ 填一张 $(n+1)\times(W+1)$ 的表。时间 $O(nW)$ ，空间 $O(nW)$ 。

空间优化的精妙之处：注意 $\text{OPT}(i,\cdot)$ 只依赖 $\text{OPT}(i-1,\cdot)$ （上一行），所以只需保留两行（甚至一行，若 $c$ 反向遍历）就能滚动计算，空间降到 $O(W)$ 。这是背包问题的经典优化，面试常考：

KNAPSACK-01
    dp[0..W] = 0
    for i = 1 to n:
        for c = W downto w[i]:   // 关键：c 反向遍历！
            dp[c] = max(dp[c], v[i] + dp[c - w[i]])
    return dp[W]

为什么 $c$ 要反向遍历？ 因为"拿第 $i$ 个"要用到 $\text{OPT}(i-1, c-w_i)$ ——即上一行的值。若 $c$ 正向遍历， $dp[c-w_i]$ 可能已被本行更新过（变成 $\text{OPT}(i, c-w_i)$ ），就变成"物品可重复拿"（完全背包）了。反向遍历保证用到的是还没被本行覆盖的旧值（上一行），维持 0/1 语义。这个细节是 0/1 背包和完全背包的唯一差别。

5.复杂度的微妙之处：伪多项式

$O(nW)$ 看着像多项式，但有个理论陷阱： $W$ 是输入数值（容量大小），不是输入规模（表示 $W$ 所需的比特数 $\log W$ ）。如果 $W$ 是 $n$ 的指数级（比如 $W=2^n$ ），算法实际是指数于输入规模的。这种"看上去多项式、实则是数值的多项式"叫伪多项式（pseudo-polynomial）。

这一点第八卷 8.6 会专门讲——它是理解"为什么子集和（背包的变种）是 NP 完全的、但又有 DP 解"的关键。DP 的 $O(nW)$ 对工程上常见的 $W$ （几千几万）很实用，但理论上它不是"真正的多项式算法"。这个区别很重要，先记住。

6.背包家族

0/1 背包是背包家族的核心，变体极多：

完全背包：每种物品无限个。 $c$ 正向遍历即可（见第 4 节反向的解释）。
多重背包：第 $i$ 种物品有 $s_i$ 个。可用二进制拆分优化。
分组背包：物品分互斥组，每组最多选一个。

它们的骨架都是 0/1 背包的状态转移思路，只是"物品可用次数"的约束不同。掌握 0/1 背包，其余变体是顺水推舟。

7.练习

Q1. 容量 $W=10$ ，物品 (重3值4)、(重4值5)、(重5 value6)，用 DP 求 $\text{OPT}$ 表的最大价值和具体拿法。

填表： $\text{OPT}(1,3..10)=4$ ；考虑物品2， $\text{OPT}(2,7)=\max(4,5+4)=9$ （拿两个）； $\text{OPT}(3,10)=\max(\text{OPT}(2,10), 6+\text{OPT}(2,5))$ 。 $\text{OPT}(2,5)=\max(4,5)=5$ ， $\text{OPT}(2,10)=9$ ，故 $\text{OPT}(3,10)=\max(9, 6+5)=11$ 。最大价值 11，拿法：物品1+2+... 验证：3+4+5=12>10 超重；最优是物品1+物品3（重8值10）或物品1+物品2（重7值9）... 实际最优为物品1(4)+物品2(5)=9或物品2(5)+物品3(6)... 重9≤10值11。故物品2+物品3，重 4+5=9≤10，值 5+6=11。（具体取决于实现，关键是转移正确。）

Q2. 0/1 背包的一维空间优化里，内层循环为什么必须 $c$ 从 $W$ 反向遍历到 $w_i$ ？正向会怎样？

因为"拿第 $i$ 个"用 $\text{OPT}(i-1, c-w_i)$ （上一行的旧值）。若 $c$ 正向遍历， $dp[c-w_i]$ 可能已被本行更新（变成 $\text{OPT}(i,c-w_i)$ ），相当于"物品 $i$ 被重复拿了"，退化成完全背包。反向遍历保证用到的是还没被本行覆盖的旧值，维持每个物品只拿一次的 0/1 语义。这是 0/1 和完全背包的唯一差别。

Q3.（思考题） 0/1 背包 DP 是 $O(nW)$ ，为什么说它是"伪多项式"而非多项式？

因为 $W$ 是输入的数值，不是输入规模（表示 $W$ 需 $\log W$ 比特）。若 $W=2^n$ ， $O(nW)=O(n\cdot2^n)$ 实际指数于输入比特数。算法时间多项式于数值而非编码长度，称伪多项式。这对理解"子集和是 NP 完全的、却有 DP"至关重要（8.6 节）——DP 实用但非"真正多项式"。

8.小结

0/1 背包用二维状态 $\text{OPT}(i,c)$ 和"拿/不拿"转移， $O(nW)$ 求解，可一维滚动优化到 $O(W)$ （ $c$ 反向遍历是关键）。贪心因贪心选择性质失效而不可用。它的 $O(nW)$ 是伪多项式（多项式于数值非编码），是理解 NP 完全性的入口。下一篇看 DP 的另一经典——最长公共子序列。