背包容量有限，物品各有重量和价值——用同一个 dp 框架，解决"每件东西能不能选、能选几次"这三种变体。
有一个容量为 W 的背包，有 n 件物品，每件物品有重量和价值。要在不超过背包容量的前提下，选一部分物品装进背包，使得装进去的物品总价值最大。这是"背包问题"最基本的描述——听起来和 13.1 节的 LIS、LCS 差别很大，但仍然可以用同一套 DP 框架解决，区别在于：这次的状态除了"考虑到第几件物品"，还要多一维"当前用掉了多少容量"。
本节统一用这组物品来演示三种背包的区别：
01 背包：每件物品要么选（1），要么不选（0），最多选一次。设 dp[i][j] 表示只考虑前 i 件物品、背包容量为 j 时能装下的最大价值。对第 i 件物品，只有两种选择：
不选第 i 件： dp[i][j] = dp[i-1][j]
容量 j 完全没动，答案直接沿用"只考虑前 i-1 件物品"时的结果。
选第 i 件（前提 j ≥ w[i]）： dp[i][j] = dp[i-1][j-w[i]] + v[i]
先"花掉" w[i] 的容量装下第 i 件物品，剩下 j-w[i] 的容量交给前 i-1 件物品去发挥，最后把这件物品的价值 v[i] 加上。
两种选择都可行时，取价值更大的： dp[i][j] = max( dp[i-1][j], dp[i-1][j-w[i]] + v[i] )
背包容量 W = 5，用①的三件物品填出完整的 dp 表（第 0 行是"一件物品都不考虑"的边界，全部是 0）：
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 件 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1（w2v3） | 0 | 0 | 3 | 3 | 3 | 3 |
| 2（w3v4） | 0 | 0 | 3 | 4 | 4 | 7 |
| 3（w4v5） | 0 | 0 | 3 | 4 | 5 | 7 |
dp[3][5] = 7 就是最终答案——选物品 1 和物品 2（重量 2+3=5 正好装满，价值 3+4=7）。第 3 行的 dp[3][5] = 7 和上一行的 dp[2][5] = 7 相同，说明加入物品 3 之后并没有更优的选法（物品 3 单独重量就是 4，装了它之后只剩 1 的容量，塞不下任何东西，4+0=4，不如已有的 7）。拿 dp[2][5] 具体展开看：
| 选择 | 算式 | 结果 |
|---|---|---|
| 不选物品 2 | dp[1][5] | 3 |
| 选物品 2（容量够，5≥3） | dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 | 7（最大） |
| 1 | int w[105], v[105], dp[105][1005], n, W; |
| 2 | |
| 3 | int ZeroOneKnapsack() |
| 4 | { |
| 5 | for (int i = 1; i <= n; i++) // 物品从 1 到 n（下标 1 开始，方便对应第 0 行边界） |
| 6 | { |
| 7 | for (int j = 0; j <= W; j++) // 容量从 0 到 W |
| 8 | { |
| 9 | dp[i][j] = dp[i-1][j]; // 默认：不选第 i 件 |
| 10 | if (j >= w[i]) // 容量够，才有"选第 i 件"这个选项 |
| 11 | dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]); |
| 12 | } |
| 13 | } |
| 14 | return dp[n][W]; |
| 15 | } |
观察转移方程会发现：dp[i][*] 这一行只依赖上一行 dp[i-1][*]，从来不会用到更早的行。既然每次只需要"上一行"，就没必要把 n 行全部存下来——用一个一维数组 dp[j] 反复覆盖更新即可，能把空间从 O(n×W) 降到 O(W)。但压缩之后，容量 j 必须从大到小遍历：
dp[5] 时用到的 dp[5-3]=dp[2]，此时 dp[2] 必须还是"上一件物品"算出的旧值。如果从左往右更新（j 从小到大），dp[2] 会在更新 dp[5] 之前就已经被同一件物品更新过一次，等于让同一件物品被用了两次——这正是 01 背包"只能选一次"这个限制被破坏的地方。从右往左更新，能保证用到的 dp[j-w[i]] 永远是"还没处理这件物品"时的旧值。| 1 | int dp[1005]; // 只保留一维，dp[j] 随物品的处理不断被覆盖 |
| 2 | |
| 3 | int ZeroOneKnapsack1D() |
| 4 | { |
| 5 | for (int i = 1; i <= n; i++) |
| 6 | { |
| 7 | for (int j = W; j >= w[i]; j--) // ★ 倒序：从 W 往 w[i] 递减 |
| 8 | dp[j] = max(dp[j], dp[j-w[i]] + v[i]); |
| 9 | } |
| 10 | return dp[W]; |
| 11 | } |
完全背包：每种物品的数量不限，只要容量够，可以一直重复选同一件。转移方程和 01 背包几乎一样，唯一的区别是"选第 i 件"之后，容量里剩下的部分仍然可以继续选第 i 件（而不是像 01 背包那样必须交给"上一件物品"）：
01 背包： dp[i][j] = max( dp[i-1][j], dp[i-1][j-w[i]] + v[i] )
完全背包： dp[i][j] = max( dp[i-1][j], dp[i][j-w[i]] + v[i] )
"选第 i 件"之后，用的是 dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]——也就是说，剩下的容量仍然可以再选一次第 i 件，选几次都不限制，直到容量不够为止。
还是①的三件物品，把容量放大到 W = 8，感受一下"可以重复选"带来的差别：
dp[8] = 12——最优选法是把物品 1 选 4 次（重量 2×4=8 正好装满，价值 3×4=12），比 01 背包能达到的最优解（每种最多一件，容量 8 时最多凑出物品2+物品3＝3+4=7 的重量、4+5=9 的价值）要高得多。这正是"可以重复选"带来的优势，也是完全背包和 01 背包本质的区别。| 1 | int dp[1005]; |
| 2 | |
| 3 | int CompleteKnapsack() |
| 4 | { |
| 5 | for (int i = 1; i <= n; i++) |
| 6 | { |
| 7 | for (int j = w[i]; j <= W; j++) // ★ 正序：从 w[i] 往 W 递增，唯一和 01 背包不同的地方 |
| 8 | dp[j] = max(dp[j], dp[j-w[i]] + v[i]); |
| 9 | } |
| 10 | return dp[W]; |
| 11 | } |
dp[j] 用到的 dp[j-w[i]]，如果 j-w[i] >= w[i]，那么 dp[j-w[i]] 在正序遍历中已经被这一轮的物品 i 更新过——也就是说它已经包含了"再选一次物品 i"的可能性。这和 01 背包倒序遍历的目的正好相反：01 背包要避免用到"这一轮已经更新过"的值，完全背包恰恰要利用这一点来实现"重复选"。这一个遍历方向的差异，是初学者最容易搞混、也是最值得记住的细节。多重背包介于两者之间：每种物品有一个确定的库存上限 c[i]，最多只能选 c[i] 次，不能像完全背包那样无限选，也不像 01 背包那样只能选一次。
最直接的想法：把"数量为 c[i] 的第 i 件物品"拆成 c[i] 个完全相同、各自独立的物品，每个只能选一次——这样问题就变回了 01 背包，直接套用 ② 的代码即可：
| 1 | // 假设物品 i 的数量上限是 c[i]，拆成 c[i] 份，每份重量 w[i]、价值 v[i]，各自独立 |
| 2 | for (int i = 1; i <= n; i++) |
| 3 | for (int k = 1; k <= c[i]; k++) // 拆成 c[i] 份 |
| 4 | for (int j = W; j >= w[i]; j--) // 和 01 背包一样，倒序遍历 |
| 5 | dp[j] = max(dp[j], dp[j-w[i]] + v[i]); |
例如物品 1 限购 2 件、物品 2 限购 1 件、物品 3 限购 1 件，容量 W = 8：最优选法是物品 1 选 2 次 + 物品 3 选 1 次（重量 2×2+4=8 正好装满，价值 3×2+5=11），比完全背包的 12（物品 1 不限量选 4 次）要少，因为这里物品 1 最多只能选 2 次。
O(W × Σc[i])——如果 c[i] 很大（比如上千），拆出来的物品数量会非常多，容易超时。存在一种二进制拆分的优化：把数量 c[i] 拆成 1, 2, 4, 8, … 这样的若干"打包物品"（每一份打包物品的重量、价值是原物品的若干倍），只需要 O(log c[i]) 份打包物品，就能通过 01 背包的方式组合出 0~c[i] 之间任意的选取数量。这个技巧涉及"为什么二进制拆分能覆盖所有可能数量"的证明，超出本节范围，这里先了解"多重背包可以用 01 背包 + 二进制拆分做到更优复杂度"这个方向即可。| 类型 | 每种物品能选几次 | 一维数组遍历顺序 |
|---|---|---|
| 01 背包 | 最多 1 次 | 容量 倒序（W → w[i]） |
| 完全背包 | 不限次数 | 容量 正序（w[i] → W） |
| 多重背包 | 最多 c[i] 次 | 拆分成 01 背包后倒序；或二进制拆分优化 |
dp 全部初始化为 0）求的是"不超过容量、价值最大"，允许背包有剩余空间。如果题目要求"恰好装满容量 W"，初始化要改成：dp[0] = 0，其余 dp[1..W] 全部设为负无穷（表示"这个容量目前还凑不出来，不合法"），转移方程不变——这样最后 dp[W] 如果还是负无穷，说明根本凑不出"恰好装满"的方案。k 每增加一次（拆出一份新物品），对应的 j 循环仍然要从 W 倒序到 w[i]，不能偷懒只在最外层判断一次。