14 背包问题专题拓展
GESP C++ 六级：背包问题专题拓展
核心目标：在掌握 01 背包与完全背包的基础上，系统掌握方案数背包、分组背包、多重背包与二进制优化、混合背包、多维背包五类变形模型，建立“看到题面 → 识别模型 → 套用模板”的场景识别能力。
背包家族的区分只看三件事——每件物品能用几次、物品之间有没有分组约束、dp 数组存的是价值还是方案数；01 背包倒序，完全背包正序，分组背包最内层遍历组内物品，方案数背包把 max 改成加法。
一、背包家族全景图
| 模型 | 物品使用次数 | 核心转移 | 循环特征 |
|---|---|---|---|
| 01 背包 | 每件最多 1 次 | dp[j] = max(dp[j], dp[j-w]+v) |
容量倒序 |
| 完全背包 | 每件无限次 | 容量正序 | |
| 多重背包 | 每件有固定数量 k | 二进制拆分后转为 01 背包 | 拆分后倒序 |
| 分组背包 | 每组最多选 1 件 | 枚举组内物品，取最优 | 组 → 容量倒序 → 组内物品 |
| 方案数背包 | 同 01/完全 | dp[j] += dp[j-w] |
与对应背包一致 |
| 混合背包 | 每件类型不同 | 按类型分别处理 | 01 倒序，完全正序 |
场景识别口诀：“一个物品能用几次？”→ 01（1次）/ 完全（无限）/ 多重（有限次）；“物品有没有分组？”→ 分组背包；“问最大价值还是方案数？”→ 价值背包用 max，方案数背包用加法。
二、方案数背包
2.1 核心思想
方案数背包不再问“最大价值是多少”，而是问“恰好装满容量 j 的方案有多少种”。核心变化只有一处：把状态转移从 max 改为加法。
终极口诀：价值背包求最优，状态转移用 max；方案背包数方法，状态转移改加法。dp[0] 最为重要，空方案要记牢！
2.2 01 背包方案数
状态：dp[j] 表示恰好装满容量 j 的方案数。
初始化：dp[0] = 1（什么都不选也是一种方案），其余 dp[j] = 0。
转移：dp[j] += dp[j-w[i]]，容量倒序。
int dp[10005] = {0};
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = W; j >= w[i]; j--) { // 倒序，每件只用一次
dp[j] += dp[j - w[i]];
}
}
cout << dp[W] << endl;
经典例题： 小A点菜——有 M 元，N 道菜，每道菜价格 v[i]，问恰好把 M 元花完的点菜方案有多少种。这是求恰好装满方案数的模板题。
2.3 完全背包方案数
与 01 方案数背包的唯一区别：容量正序遍历。
int dp[10005] = {0};
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= W; j++) { // 正序，物品可重复使用
dp[j] += dp[j - w[i]];
}
}
cout << dp[W] << endl;
经典应用：硬币问题——有 1 元、2 元、5 元硬币无限个，问组成 10 元有多少种方案。
2.4 方案数背包的初始化对比
| 问法 | dp[0] | 其余 | 遍历方向 |
|---|---|---|---|
| 01 方案数（恰好装满） | 1 | 0 | 倒序 |
| 完全方案数（恰好装满） | 正序 | ||
| 最大价值（不要求装满） | 0 | 依背包类型 | |
| 最大价值（恰好装满） | -INF |
关键提醒：方案数背包中 dp[0] = 1 是最容易出错的地方。很多同学会误以为“凑出重量 0 有 0 种方法”，实际上“什么都不选”就是一种方案。
三、分组背包
3.1 问题模型
物品被分成若干组，每组最多只能选一个物品（也可以一个都不选）。例如选课系统中“数学组选一门、英语组选一门、科学组选一门”。
口诀：每组最多挑一个，组内物品不能叠。
3.2 状态定义
dp[j] 表示前 i 组物品、容量为 j 时的最大价值。注意：这里的 i 表示的是前 i 组，而不是前 i 件物品——这是最容易混淆的地方。
3.3 转移方程与循环结构
对于第 i 组，组内有若干物品。对容量 j，尝试组内每一个物品，取最优：
三层循环结构：最外层枚举组，中间层倒序枚举容量，最内层枚举组内物品。
for (int i = 1; i <= g; i++) { // 外层：枚举组
for (int j = W; j >= 0; j--) { // 中间：容量倒序
for (int k = 0; k < group[i].size(); k++) { // 内层：组内物品
int w = group[i][k].w, v = group[i][k].v;
if (j >= w) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
}
}
cout << dp[W] << endl;
为什么中间层容量要倒序？ 倒序保证每个物品最多被选一次（每组最多选一个），如果正序，同一组的物品可能会被重复选择，退化为完全背包。
3.4 一维优化写法
int dp[10005] = {0};
for (int i = 1; i <= g; i++) {
for (int j = W; j >= 0; j--) {
for (auto &item : group[i]) {
if (j >= item.w) {
dp[j] = max(dp[j], dp[j - item.w] + item.v);
}
}
}
}
注意：分组背包的“每组最多选一个”约束，使得内层遍历组内物品时不能直接套用 01 背包的模板。必须保证同一组的物品不会在同一轮容量循环中被重复选中，因此容量倒序是必需的。
3.5 真题对接：学习小组
将 n 名学生分成若干个连续编号的小组，每个小组人数为 i 时有对应的奖励值 a[i]。这道题容易被误判为 01 背包，但题目并未限制小组人数不能重复，因此同一人数的小组可以出现多次——这是完全背包，而不是分组背包。
四、多重背包与二进制优化
4.1 问题模型
每件物品有固定数量 k 个，可以选择 0 到 k 个。例如“宝剑有 3 把”。
4.2 朴素解法
把 k 个相同物品看作 k 件独立的 01 背包物品，逐一处理。复杂度 O(n × W × k)，当 k 较大时会超时。
4.3 二进制拆分优化（核心）
核心思想：把 k 件相同物品拆分成若干“捆”，每捆的数量是 1、2、4、8……这样的 2 的幂次。
为什么是 2 的幂：任何正整数都可以表示为若干个 2 的幂之和。例如 13 = 1 + 4 + 8（或 1 + 2 + 4 + 6）。通过这种方式，可以用 O(log k) 个“捆绑物品”表示 0~k 的任意数量选择。
拆分规则：设剩余数量为 rem，当前拆分大小为 p = 1：
int rem = k, p = 1;
while (rem > 0) {
int take = min(p, rem);
// 将 take 个物品打包成一个新物品
w_new = take * w[i];
v_new = take * v[i];
// 这个新物品按 01 背包处理
rem -= take;
p *= 2;
}
举例：k = 13，拆分过程：1, 2, 4, 6（剩余 13-1-2-4=6，最后一块直接取剩余）。
拆分后，对每个“捆绑物品”执行 01 背包的容量倒序遍历即可。
4.4 完整代码模板
int dp[10005] = {0};
for (int i = 1; i <= n; i++) {
int k = cnt[i]; // 第 i 种物品的数量
int p = 1;
while (k > 0) {
int take = min(p, k);
int w_new = take * w[i];
int v_new = take * v[i];
// 01 背包处理
for (int j = W; j >= w_new; j--) {
dp[j] = max(dp[j], dp[j - w_new] + v_new);
}
k -= take;
p *= 2;
}
}
cout << dp[W] << endl;
复杂度：O(n × W × log k)，远优于朴素解法。
4.5 真题对接：道具商店（GESP202512 六级 ）
这道题涉及用金币提升攻击力，物品有数量限制，需要多重背包或二进制优化处理。
五、混合背包
5.1 问题模型
一个背包问题中同时出现多种类型的物品——有的只能选一次（01），有的可以无限选（完全），有的有固定数量（多重）。
5.2 核心思想
混合背包没有新的 DP 模型。它的本质是：按物品类型分别处理，每种物品套用对应背包的循环模板即可。
输入格式识别：题目通常用 s 表示物品类型：
s = -1：01 背包，只能选一次s = 0：完全背包，无限选s > 0：多重背包，有 s 个
5.3 统一处理模板
for (int i = 1; i <= n; i++) {
if (type[i] == 1) { // 01 背包
for (int j = W; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
} else if (type[i] == 0) { // 完全背包
for (int j = w[i]; j <= W; j++) {
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
} else { // 多重背包
int k = cnt[i], p = 1;
while (k > 0) {
int take = min(p, k);
int w_new = take * w[i], v_new = take * v[i];
for (int j = W; j >= w_new; j--) {
dp[j] = max(dp[j], dp[j-w_new] + v_new);
}
k -= take;
p *= 2;
}
}
}
5.4 真题对接：小杨买饮料（GESP 六级）
涉及多种类型的物品混合，需要根据每件物品的类型选择对应的循环方向。
六、多维背包（了解）
6.1 问题模型
每个物品不仅消耗一种资源（如体积），还消耗另一种资源（如重量），背包对两种资源都有上限。
6.2 核心思路
状态数组升维：dp[j][k] 表示第一种资源为 j、第二种资源为 k 时的最大收益。转移时两层容量都倒序（01 背包）。
for (int i = 1; i <= n; i++) {
for (int j = W1; j >= w1[i]; j--) {
for (int k = W2; k >= w2[i]; k--) {
dp[j][k] = max(dp[j][k], dp[j-w1[i]][k-w2[i]] + v[i]);
}
}
}
六级对多维背包的考查较少，了解状态升维的思路即可。
七、场景识别速查表
看到一道背包题时，按以下顺序判断：
| 判断问题 | 答案 | 模型 |
|---|---|---|
| 问最大价值还是方案数？ | 方案数 | 方案数背包（转移改加法） |
| 每件物品能用几次？ | 1 次 | 01 背包（容量倒序） |
| 无限次 | 完全背包（容量正序） | |
| 固定 k 次 | 多重背包（二进制拆分→01） | |
| 物品有分组吗？ | 每组最多选一个 | 分组背包（组→容量倒序→组内物品） |
| 多种类型混合？ | 01+完全+多重 | 混合背包（按类型分别处理） |
| 消耗多种资源？ | 体积+重量等 | 多维背包（状态升维） |
终极口诀：“一个物品能用几次？”——这是看到背包题时第一个要问自己的问题。
八、易错点汇总
- 方案数背包 dp[0] 初始化为 0：应该为 1（空方案是一种方案）。
- 分组背包容量正序遍历：会导致同组物品被重复选择，必须倒序。
- 多重背包不拆分直接当 01 背包：k 较大时超时，必须二进制拆分。
- 二进制拆分最后一块忘记取 min：
take = min(p, rem)，不是直接取p。 - 混合背包中完全背包用倒序：完全背包必须正序，倒序会退化为 01 背包。
- 多维背包容量循环方向：01 多维背包两层容量都倒序，完全多维背包都正序。
- 方案数背包用 max 而非加法：方案数的转移是
+=，不是max。 - 方案数溢出：方案数可能很大，通常需要对
10^9+7取模。 - 分组背包状态定义混淆：
dp[i][j]中的 i 是“前 i 组”，不是“前 i 件物品”。 - 混合背包类型识别错误：
s = -1是 01，s = 0是完全，s > 0是多重。
九、总结
背包问题专题拓展是 GESP 六级动态规划模块的“最后一公里”。
- 背包家族的区分只看三件事：物品能用几次、有没有分组、dp 存价值还是方案数。
- 方案数背包的核心变化：把
max改为+=，dp[0] = 1。 - 01 方案数倒序，完全方案数正序，与价值背包的循环方向完全一致。
- 分组背包：每组最多选一个，三层循环“组 → 容量倒序 → 组内物品”。
- 多重背包：二进制拆分把 k 件物品拆成 O(log k) 个捆绑物品，再按 01 背包处理。
- 混合背包没有新模型，按物品类型分别套用 01 / 完全 / 多重模板。
- 多维背包：状态升维，
dp[j][k]表示两种资源分别为 j 和 k。 - 看到背包题先问“一个物品能用几次”，这是识别模型的第一把钥匙。
- 分组背包的 i 是“前 i 组”，不是“前 i 件物品”，这是最容易混淆的地方。
- 多练“小A点菜（方案数）”“学习小组（完全）”“道具商店（多重）”“小杨买饮料（混合）”四类题。
复习建议：先把 01 背包和完全背包的模板写熟，确保闭卷能默写；再重点攻克方案数背包，牢记 dp[0]=1 和加法转移；然后练习分组背包的三层循环和多重背包的二进制拆分；最后用“道具商店”“小杨买饮料”等真题做场景识别训练，看到题面能快速判断属于哪一类背包。考试中先判断“物品能用几次”，再判断“有没有分组”，最后判断“求价值还是方案数”，三步锁定模型后套用对应模板。