跳转到内容
← 返回算法
经典算法计算机科学 · 动态规划 · 组合优化约 23 分钟阅读

背包问题

Knapsack Problem

一位探险家准备出发，背包最多承重 $W$ 公斤。他面前有 $n$ 件宝物，每件有重量 $wi$ 和价值 $vi$。他应该带哪些宝物，才能让总价值最大，同时不超过背包承重？ 这就是著名的0-1 背包问题（0-1 Knapsack Problem）——"0-1"意味着每件物品要么完整带走（1），要么完全不带（0），不能只带…

背包问题动态规划NP完全组合优化

一位探险家准备出发，背包最多承重 $W$ 公斤。他面前有 $n$ 件宝物，每件有重量 wiw_i 和价值 viv_i。他应该带哪些宝物，才能让总价值最大，同时不超过背包承重？

这就是著名的0-1 背包问题（0-1 Knapsack Problem）——"0-1"意味着每件物品要么完整带走（1），要么完全不带（0），不能只带一部分。看起来简单，但它是 NP 完全问题。理解背包问题，就是理解为什么有些优化问题在计算上是"困难的"，以及动态规划如何在实践中给出精确解。

破除误解：贪心无法解 0-1 背包

直觉上，按"价值密度"（vi/wiv_i / w_i，每公斤价值）从高到低贪心选取，似乎合理。但这对 0-1 背包是错的。

反例：背包容量 $W = 7$

物品重量价值密度
A430.75
B320.67
C540.80

贪心：先选密度最高的 C（重 5，价值 4），剩余容量 2，A 和 B 都放不下——总价值 4。最优：选 A + B（重 4+3=7，恰好装满），总价值 5 > 4。

贪心之所以失败，是因为它只看"单位价值"，看不到"用整数件物品恰好填满容量"这一组合约束。贪心对分数背包（可以按比例取物品的一部分）给出精确最优解，但对 0-1 背包无效。

动态规划解法

状态定义：$dp[i][j]$ = 考虑前 $i$ 件物品，背包容量为 $j$ 时的最大价值。递推关系：

dp[i][j]={dp[i−1][j]若 wi>j（第 i 件放不下）max⁡(dp[i−1][j], dp[i−1][j−wi]+vi)若 wi≤jdp[i][j] = \begin{cases} dp[i-1][j] & \text{若 } w_i > j \text{（第 } i \text{ 件放不下）} \\ \max(dp[i-1][j],\ dp[i-1][j-w_i] + v_i) & \text{若 } w_i \leq j \end{cases}

直觉：第 $i$ 件物品的选择只有两种——不选（沿用前 $i-1$ 件的最优解），或选（前 $i-1$ 件在容量 j−wij - w_i 下的最优值 + 第 $i$ 件价值）。填满一张 n×Wn \times W 的表格即可，时间复杂度 $O(nW)$。

空间优化：由于 $dp[i]$ 只依赖 $dp[i-1]$，可用一维数组滚动更新，空间降至 $O(W)$：

python
dp = [0] * (W + 1)
for i in range(n):
    for j in range(W, w[i] - 1, -1):  # 从大到小，防止重复使用
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
```

注意：从大到小遍历容量是关键——若从小到大，同一件物品可能被多次使用（变成"无限背包"）。这句话几乎每本教材都写，但很少有人把它算给你看。下面两节就把这两件事逐格算完。

手算一张完整的 DP 表

四件物品，背包容量 $W = 8$：

物品重量 $w$价值 $v$密度 $v/w$
A231.50
B341.33
C451.25
D581.60

先看贪心会怎么做：密度最高的是 D，装进去（重 5，值 8），余量 3；下一个密度最高的是 A，装进去（重 2，值 3），余量 1；B、C 都放不下。贪心答案 11，占用 7 公斤，还空着 1 公斤。记住这个数，下面 DP 会给出 12。

按物品顺序 A→B→C→D 逐行填表。行是"考虑前 $i$ 件"，列是容量 $j$：

前 $i$ 件 \ 容量 $j$012345678
$i=0$（什么都不考虑）000000000
$i=1$（加入 A：2/3）003333333
$i=2$（加入 B：3/4）003447777
$i=3$（加入 C：4/5）003457899
$i=4$（加入 D：5/8）00345881112

粗体是"这一格因为选了新物品而变大"的位置。挑五个格子把判断写全，每一格都只查上一行的两个数：

格子不取新物品：$dp[i-1][j]$取新物品：dp[i−1][j−wi]+vidp[i-1][j-w_i]+v_i谁大结果
$dp[2][5]$$dp[1][5]=3$$dp[1][2]+4=3+4=7$取7
$dp[3][5]$$dp[2][5]=7$$dp[2][1]+5=0+5=5$不取7
$dp[3][6]$$dp[2][6]=7$$dp[2][2]+5=3+5=8$取8
$dp[4][6]$$dp[3][6]=8$$dp[3][1]+8=0+8=8$打平，按惯例不取8
$dp[4][8]$$dp[3][8]=9$$dp[3][3]+8=4+8=12$取12

最优值 $dp[4][8] = 12$，比贪心的 11 多 1。这张表最该注意的是 $dp[3][5]=7$ 那一格：容量 5 恰好能装下 C（重 4）还余 1，但表格告诉你不要装——因为 A+B（重 5，值 7）已经把这 5 公斤用得更好。贪心没有"回头看"的能力，DP 有，因为它把"容量 5 之前最好能做到多少"这个中间答案存下来了。

从表格回溯出选了哪几件。DP 表只给出最大值，物品清单要靠比较相邻两行倒推：如果 dp[i][j]≠dp[i−1][j]dp[i][j] \neq dp[i-1][j]，说明第 $i$ 件被选中了。

步当前格上一行同列判断跳到
1$dp[4][8]=12$$dp[3][8]=9$不等 → D 被选中$dp[3][8-5]=dp[3][3]$
2$dp[3][3]=4$$dp[2][3]=4$相等 → C 没选$dp[2][3]$
3$dp[2][3]=4$$dp[1][3]=3$不等 → B 被选中$dp[1][3-3]=dp[1][0]$
4$dp[1][0]=0$$dp[0][0]=0$相等 → A 没选结束

答案是 {B,D}\{B, D\}：重 $3+5=8$，恰好装满，价值 $4+8=12$。注意贪心选的是 {D,A}\{D, A\}——两个方案都拿了 D，分歧只在第二件；贪心图 A 的密度高（1.50 > 1.33），DP 看的是"剩下 3 公斤怎么用最值"，而 3 公斤刚好是 B 的尺码。

这个回溯步骤解释了为什么一维滚动数组有代价：滚动数组只留最后一行，上面这四步比较就没得比了。要输出物品清单，必须留完整的二维表（$O(nW)$ 空间），或者额外记一张 n×Wn \times W 的布尔"是否选取"表。工程上如果只需要最大值，用一维；需要方案，就得付空间。

一维数组的方向：一张小表说清正序与倒序

只用一件物品就能看清方向的影响。设物品 $w=2, v=3$，$W=6$，一维数组初始全 0。

正序（$j$ 从 2 增到 6）：

当前 $j$23456
读到的 $dp[j-2]$$dp[0]=0$$dp[1]=0$$dp[2]=3$（本轮刚写）$dp[3]=3$（本轮刚写）$dp[4]=6$（本轮刚写）
写入 $dp[j]$33669

$dp[6]=9$ 意味着这件物品被拿了三次（3×3=93 \times 3 = 9，重 3×2=63 \times 2 = 6）。

倒序（$j$ 从 6 减到 2）：

当前 $j$65432
读到的 $dp[j-2]$$dp[4]=0$（上一轮的值）$dp[3]=0$$dp[2]=0$$dp[1]=0$$dp[0]=0$
写入 $dp[j]$33333

全部是 3，物品只被拿了一次。两张表的差别只有一句话：正序时 $dp[j-w]$ 已经是"本轮更新过的值"（包含了这件物品），倒序时它还是"上一轮的值"（不含这件物品）。

递推式里写的是 dp[i−1][j−wi]dp[i-1][j-w_i]，下标是 $i-1$——一维数组要模拟这个"上一行"，就必须保证读到的格子还没被本轮碰过，所以倒序。反过来，完全背包要的恰恰是"可以重复拿"，也就是 dp[i][j−wi]dp[i][j-w_i]（同一行），所以正序。这是同一份三行代码，改一个方向就换了一个问题。

背包变种

完全背包（Unbounded Knapsack）

每件物品可以取任意多件。只需将 $j$ 的遍历方向改为从小到大：

python
for i in range(n):
    for j in range(w[i], W + 1):  # 从小到大！
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
```

有限背包（Bounded Knapsack）

每件物品 $i$ 最多取 cic_i 次。朴素方法：展开为 cic_i 件相同物品的 0-1 背包，O(n⋅c⋅W)O(n \cdot c \cdot W)（$c$ 为平均数量）。

优化：二进制分组——将 cic_i 件物品分组为 1,2,4,…1, 2, 4, \ldots 件（二进制表示），每组视为一件新物品，做 0-1 背包，复杂度降至 O(nlog⁡c⋅W)O(n \log c \cdot W)。举个具体的：ci=13c_i = 13 时拆成 $1, 2, 4, 6$ 四组（前三组是 $1+2+4=7$，最后一组补上 $13-7=6$），这四个数的子集和恰好覆盖 $0$ 到 $13$ 的每个整数，一件不多一件不少——于是"最多取 13 次"被 4 件虚拟物品完整表达。

多维背包

背包有多个容量限制（如重量和体积），每件物品有对应的多个消耗。DP 扩展为多维状态 dp[i][j1][j2]dp[i][j_1][j_2]，时间 O(n⋅W1⋅W2)O(n \cdot W_1 \cdot W_2)。

分组背包

物品分为若干组，每组最多选一件：

python
for k in groups:
    for j in range(W, -1, -1):
        for i in group_k:
            if j >= w[i]:
                dp[j] = max(dp[j], dp[j - w[i]] + v[i])
```

恰好装满 vs 不超过

有时要求"恰好装满"（而非"不超过"），初始化不同：

  • 不超过：dp[0] = 0，其余 $0$（允许不满）
  • 恰好装满：dp[0] = 0，其余 −∞-\infty（未能恰好装满时视为无效）

为什么 0-1 背包是 NP 完全的？

注意：$O(nW)$ 的 DP 看起来是多项式时间，为什么 0-1 背包是 NP 完全的？

伪多项式时间（Pseudo-polynomial Time）：$O(nW)$ 是关于 $n$ 和 $W$ 的多项式，但不是关于输入编码长度的多项式。输入编码长度约为 O(nlog⁡W)O(n \log W)（用二进制表示 $W$ 需要 log⁡W\log W 位）。因此 $W$ 相对于输入大小是指数级的（W=2log⁡WW = 2^{\log W}），$O(nW)$ 实际上是指数时间。

把这句话换成数字，它会立刻变得具体。 设 $n = 30$ 件物品，容量 W=240≈1.1×1012W = 2^{40} \approx 1.1 \times 10^{12}，每件物品的重量和价值也是 40 位以内的整数。那么：

  • 输入文件有多大：$30$ 件物品 ×\times 2 个 40 位整数，加上 $W$ 本身，约 $2440$ 比特——不到 310 字节，一条短信的长度。
  • DP 表有多大：30×1.1×1012≈3.3×101330 \times 1.1 \times 10^{12} \approx 3.3 \times 10^{13} 格。即便每格只占 1 字节，也要 33 TB 内存；按每秒 10910^9 次格子更新算，要跑约 9 小时。
  • 纯枚举有多大：230≈1.07×1092^{30} \approx 1.07 \times 10^9 个子集，10910^9 次运算——比 DP 快三万倍。

这就是"伪多项式"的真实含义：算法的开销跟着数值涨，而输入长度跟着位数涨，两者之间隔着一个指数。$W$ 一大，$O(nW)$ 的 DP 不但不快，反而比朴素枚举更慢。NP 完全性的本质正是这一点：没有关于输入长度的多项式时间算法（除非 P=NP，见 p-vs-np）。

反过来说，当 $W$ 数值"合理"时（如 W≤106W \leq 10^6），DP 是完全可行的精确算法。这正是背包问题在实践中被广泛应用的原因——工程上遇到的背包，容量往往是"箱子能装几百件""预算一万块"这种量级，$nW$ 小得可以忽略。

FPTAS：任意精度近似

若 $W$ 过大，可以用完全多项式时间近似方案（FPTAS，Fully Polynomial-Time Approximation Scheme）。思路要换一个方向：不再按重量建表，而是按价值建表——问"要凑出价值 $p$，最少需要多重"，然后把价值缩小到可以承受的规模。

舍入尺度怎么定。记 P=max⁡iviP = \max_i v_i，给定误差参数 ε>0\varepsilon > 0，取

K=εPn,vi′=⌊viK⌋K = \frac{\varepsilon P}{n}, \qquad v_i' = \left\lfloor \frac{v_i}{K} \right\rfloor

也就是把每件物品的价值按 $K$ 为单位向下取整。缩放后最大价值只有 ⌊P/K⌋=⌊n/ε⌋\lfloor P/K \rfloor = \lfloor n/\varepsilon \rfloor，与原始数值 $P$ 无关——这是全部关键。

误差从哪里来，为什么正好是 ε\varepsilon。每件物品向下取整最多丢掉不足 $K$ 的价值。最优解 $O$ 里至多 $n$ 件物品，所以在缩放后的世界里，$O$ 的价值最多被低估 nK=εPnK = \varepsilon P。算法在缩放世界里求出的精确最优解 $A$ 满足

v(A)≥K⋅v′(A)≥K⋅v′(O)≥v(O)−nK=OPT−εP≥(1−ε) OPTv(A) \geq K \cdot v'(A) \geq K \cdot v'(O) \geq v(O) - nK = \text{OPT} - \varepsilon P \geq (1 - \varepsilon)\,\text{OPT}

最后一步用到 P≤OPTP \leq \text{OPT}——最值钱的那一件单独装进去就是一个可行解，所以最优值不可能比它还小。误差界不是估出来的，是舍入尺度直接算出来的。

代价是时间。DP 表的规模是 $n$ 行乘以"总缩放价值"n⌊n/ε⌋n \lfloor n/\varepsilon \rfloor 列，即 O(n2⌊n/ε⌋)=O(n3/ε)O(n^2 \lfloor n/\varepsilon \rfloor) = O(n^3/\varepsilon)。代入数字看：$n = 100$、原始价值上限 P=106P = 10^6、ε=0.1\varepsilon = 0.1，则 K=0.1×106/100=1000K = 0.1 \times 10^6 / 100 = 1000，价值 $987654$ 被舍成 $987$，缩放后每件物品的价值上限是 $1000$，DP 表约 100×105=107100 \times 10^5 = 10^7 格。而如果按重量建表、容量是 10910^9，那是 101110^{11} 格——四个数量级的差别，换来的是最多 10% 的误差。想把误差压到 1%，$K$ 缩小十倍，表格涨十倍。ε\varepsilon 就是这个兑换比。

背包是少数能做到 FPTAS（可任意逼近）的 NP 难问题，处在近似难度层次的最顶端，对比见 approximation-algorithms。

这条路已经走到尽头了吗。Ibarra 与 Kim 在 1975 年给出第一个背包 FPTAS，Lawler 在 1979 年把时间改进到 O(nlog⁡(1/ε)+(1/ε)4)O(n \log(1/\varepsilon) + (1/\varepsilon)^4)，此后四十年里 1/ε1/\varepsilon 的指数被一点点往下压。2024 年，Chen、Lian、Mao 与 Zhang 在 STOC 上给出 O~(n+(1/ε)2)\tilde{O}(n + (1/\varepsilon)^2) 的算法，并证明这个界在条件下是最优的：若 (min⁡,+)(\min, +) 卷积不存在真正次二次时间的算法（这是细粒度复杂度里一个被广泛相信的猜想），那么任何 FPTAS 都不可能做到 O((n+1/ε)2−δ)O((n + 1/\varepsilon)^{2-\delta})。一个 1975 年提出的近似问题，在 2024 年被证明"到此为止"——这类"上界与条件下界会合"的结果，是近十年算法理论最有分量的进展形式之一。

子集和问题：背包的特殊情形

子集和（Subset Sum）：给定集合 $S$ 和目标值 $T$，是否存在子集使和恰为 $T$？这是背包问题 vi=wi,W=Tv_i = w_i, W = T 时的判定版本，同样 NP 完全，同样有伪多项式时间 DP 解 $O(nT)$。

子集和是密码学中"背包密码（Knapsack Cryptosystem）"的基础——Merkle 和 Hellman 在 1978 年提出，但随后被 Shamir 在 1982 年（FOCS）用格基规约方法破解，成为密码学历史上著名的失败案例。这里有个值得记住的教训："NP 完全"不等于"每个实例都难"。背包密码的公钥是从一个"超递增序列"（每项大于前面所有项之和）经模乘伪装而来的，而超递增子集和用贪心就能在线性时间解掉；伪装没能掩盖住这层结构，格基规约把它扒了出来。密码学要的是"随机实例也难"，而 NP 完全性只保证"最坏实例难"，两者之间的鸿沟埋葬了整整一代基于组合优化的密码系统。

跨域连接

  • P 与 NP：填表的代价是件数乘以容量数值，看着像多项式，但输入长度只有容量的位数——两者之间隔着一个指数，这就是伪多项式。由此推出一条实用判断：容量取值极大时，指数级的子集枚举反而比填表更快。区分"关于数值的多项式"与"关于输入长度的多项式"，正是强弱 NP 难之分的入口。
  • 线性规划：把零一变量松弛成零到一之间的实数，问题立刻变成分数背包，贪心可解，得到的最优值是整数解的上界。分支定界的全部效率来自这个界：界一旦低于已知的可行解，整枝剪掉。所以松弛得越紧、界越接近整数最优，搜索树越小——现代求解器加割平面做的正是这件事。
  • 公钥密码与 RSA：把子集和当作陷门来造公钥的尝试彻底失败了，教训很具体。NP 完全保证的是最坏实例难，密码学要的是随机实例难。那类公钥由超递增序列经模乘伪装而来，而超递增子集和用贪心就能线性时间解掉；伪装没能掩盖这层结构，格基规约把它扒了出来。两种"难"之间的鸿沟埋掉了整整一代组合密码方案。
  • 卫生经济学评价与优先级设定：按每单位成本的健康收益排序、依次纳入直到预算耗尽，正是分数背包的贪心。但医院、设备与培训项目不可分割，排序法给出的只是上界，会系统性高估既定预算能买到的健康。真实决策还带着项目之间的依赖（先有实验室才能做检测），这两条都把问题推回整数规划。
  • 预算治理：公共预算是典型的整数背包，还叠着多期与部门配额约束。松弛问题的对偶变量给出"每多一元能买到多少价值"，这就是边际支出效益的算法版本，也是判断某个项目该不该挤进来的量化依据。但政治可行性不是可加的价值，最优解常因分配格局被否决——目标函数漏项时，出错的不是最优化，而是把它当成决策。

参考文献

  • Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第16章，第35章 FPTAS）
  • Kellerer, H., Pferschy, U. & Pisinger, D. Knapsack Problems. Springer, 2004.
  • Vazirani, V. Approximation Algorithms. Springer, 2001. （第8章 Knapsack，价值舍入 FPTAS 与误差界推导）
  • Ibarra, O. H. & Kim, C. E. "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems." Journal of the ACM 22(4), 463–468 (1975).（第一个背包 FPTAS）
  • Lawler, E. L. "Fast Approximation Algorithms for Knapsack Problems." Mathematics of Operations Research 4(4), 339–356 (1979).
  • Chen, L., Lian, J., Mao, Y. & Zhang, G. "A Nearly Quadratic-Time FPTAS for Knapsack." STOC 2024, 283–294. arXiv:2308.07821.（O~(n+(1/ε)2)\tilde{O}(n+(1/\varepsilon)^2) 与条件下界）
  • Merkle, R. & Hellman, M. "Hiding Information and Signatures in Trapdoor Knapsacks." IEEE Trans. Info. Theory 24(5), 1978.
  • Shamir, A. "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem." FOCS 1982, 145–152.

延伸阅读

  • Kleinberg, J. & Tardos, É. Algorithm Design. Pearson, 2005.（第 6.4 节把背包 DP 与"按价值建表"两种视角并列讲，是理解 FPTAS 换维度思路的最好入口）
  • Pisinger, D. "Where Are the Hard Knapsack Problems?" Computers & Operations Research 32(9), 2271–2284 (2005).（哪些实例真的难：随机生成的背包大多好解，难例需要刻意构造）
  • Williams, V. V. "On Some Fine-Grained Question in Algorithms and Complexity." ICM 2018 Proceedings.（细粒度复杂度综述，含 (min⁡,+)(\min,+) 卷积猜想的位置）

正文中引用本条 · 3 · 其中 1 条来自其他领域

医学与公共卫生公平卫生优先排序：从项目排名到可复审组合