🎒 背包问题全家桶（从 0-1 出发，一网打尽）

学生请求："把所有背包问题讲明白"。
核心思想：所有背包都是 0-1 背包的变形。抓住 0-1 的本质（倒序、每件一次），其他背包就是改一两个循环的事。

---

〇、背包问题家族地图（先看全景）

0-1 背包（每件最多 1 次）★ 根基
 ├─ 完全背包（每件无限次）→ 容量正序
 ├─ 多重背包（每件有限次 c 件）→ 二进制拆分转 0-1
 ├─ 混合背包（01 + 完全 + 多重混在一起）→ 分类处理
 ├─ 二维费用背包（重量+体积两个限制）→ dp 加一维
 ├─ 分组背包（每组最多选 1 件）→ 组外循环
 └─ 依赖背包（买主件才能买附件）→ 分组背包思想/树形

规律：改"物品的使用规则"= 改遍历顺序或加维度；改"限制条件"= 加维度。

---

一、0-1 背包（复习，一切的基础）

问题：n 件物品，第 i 件重量 wᵢ、价值 vᵢ，容量 W，每件最多拿 1 次，求最大价值。

• 状态：dp[j] = 容量 j 的最大价值
• 转移：dp[j] = max(dp[j], dp[j-w] + v)
• 顺序：容量倒序（保证每件只拿一次）

vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
    int w, v; cin >> w >> v;
    for (int j = W; j >= w; j--)            // 倒序！
        dp[j] = max(dp[j], dp[j - w] + v);
}

为什么倒序：保证 dp[j-w] 是"没用过这件物品"的旧值。正序会让同一件被反复拿。

---

二、完全背包（每件无限次）

区别就一处：容量正序。

for (int i = 0; i < n; i++) {
    int w, v; cin >> w >> v;
    for (int j = w; j <= W; j++)            // 正序！
        dp[j] = max(dp[j], dp[j - w] + v);
}

为什么正序：正序时 dp[j-w] 已经被本件物品更新过，dp[j] = dp[j-w] + v 等于"再拿一件同样的"——相当于可以重复拿。

一句话：倒序 = 用过就没了（0-1）；正序 = 随便用（完全）。

---

三、多重背包（每件有限次 c 件）

问题：第 i 件物品最多拿 cᵢ 件。

方法 1：朴素拆分（把 cᵢ 件拆成 cᵢ 个"单独的 0-1 物品"）

vector<pair<int,int>> items;  // {w, v}
for (int i = 0; i < n; i++) {
    int w, v, c; cin >> w >> v >> c;
    for (int k = 0; k < c; k++) items.push_back({w, v});  // 拆开
}
// 然后对 items 跑 0-1 背包

复杂度 O(W × Σcᵢ)，c 大时会超时。

方法 2：二进制拆分（⭐ 比赛必用，O(W × Σlog cᵢ)）

思想：任何数量 c，都能用 1, 2, 4, 8, ... 的组合表示（二进制）。比如 c=13：
拆成 1 + 2 + 4 + 6（13 = 1+2+4+6，最后一项是余数 13-7=6）。
这样 13 件物品变成 4 个"打包物品"，每个打包物品还是 0-1 拿一次，但能组合出 0~13 任意数量！

vector<pair<int,int>> items;
for (int i = 0; i < n; i++) {
    int w, v, c; cin >> w >> v >> c;
    for (int k = 1; c > 0; k <<= 1) {      // k = 1,2,4,8,...
        int take = min(k, c);
        items.push_back({take * w, take * v});  // take 件打包成 1 件
        c -= take;
    }
}
// 然后对 items 跑 0-1 背包（倒序）

验证：c=13 → take: 1, 2, 4, 6。用这 4 个打包件能组合出 1~13 的任意数量 ✅

---

四、混合背包（01 + 完全 + 多重都有）

思路：读入时给每件物品打个类型标签，按类型用不同的循环方向：

vector<tuple<int,int,int>> items;  // {type, w, v}  type: 0=01, 1=完全, 2=多重(c已拆好)
// 读入后：多重先二进制拆分转成 0-1；完全保留"正序"标签；0-1 保留"倒序"标签
// 处理时：
for (auto [type, w, v] : items) {
    if (type == 0) {                 // 0-1：倒序
        for (int j = W; j >= w; j--)
            dp[j] = max(dp[j], dp[j-w] + v);
    } else {                         // 完全：正序
        for (int j = w; j <= W; j++)
            dp[j] = max(dp[j], dp[j-w] + v);
    }
}

本质：dp 数组只有一个，每个物品按自己的"使用规则"更新它，互不干扰。

---

五、二维费用背包（两个限制条件）

问题：每件物品有重量 w 和体积 t 两个限制，容量分别是 W 和 T，求最大价值。

思路：限制多一个 → dp 加一维。

• 状态：dp[j][k] = 重量 j、体积 k 时的最大价值
• 转移：dp[j][k] = max(dp[j][k], dp[j-w][k-t] + v)
• 顺序：两个维度都倒序（0-1 性质）

vector<vector<int>> dp(W+1, vector<int>(T+1, 0));
for (int i = 0; i < n; i++) {
    int w, t, v; cin >> w >> t >> v;
    for (int j = W; j >= w; j--)
        for (int k = T; k >= t; k--)
            dp[j][k] = max(dp[j][k], dp[j-w][k-t] + v);
}

规律总结：每多一个限制，dp 就多一维，循环就多一层（都要倒序）。

---

六、分组背包（每组最多选 1 件）

问题：物品分成若干组，每组最多选 1 件，求最大价值。

思路：组的循环放最外层，组内物品放中间，容量倒序放最内层：

vector<vector<pair<int,int>>> groups;  // 每组若干 {w, v}
for (auto &g : groups) {               // ① 组在外
    for (int j = W; j >= 0; j--) {     // ② 容量倒序
        for (auto [w, v] : g) {        // ③ 组内物品
            if (j >= w)
                dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
}

为什么组在外、容量在中：保证每组只"决策一次"（从组里选 0 或 1 件）。容量倒序保证组内物品不会互相叠加。

对比：如果容量放最外层，同一组的多件物品可能都被选中（错）。

---

七、依赖背包（买主件才能买附件）— 了解即可

问题：买相机（主件）才能买镜头（附件）。每组"主件 + 附件"选法有限（都不买 / 只买主件 / 主+附件组合）。

思路（分组背包思想）：把每个主件及其附件的所有合法组合当成一组：

比如主件 A + 附件 a1 + a2，合法组合：

• 都不买（0 件）
• 只买 A
• 买 A + a1
• 买 A + a2
• 买 A + a1 + a2

把每个组合当成一个"物品"（重量=组合总重量，价值=组合总价值），然后跑分组背包（每组选 0 或 1 个组合）。

洛谷 P1064 金明的预算方案就是这个题，网络赛很少直接考，了解思想即可。

依赖背包参考代码（P1064 思路）

P1064 特点：每个主件最多 2 个附件，附件必须配主件。把每个主件+附件的所有组合枚举成"打包物品"，再跑分组背包：

// 思路版代码（P1064：n 主件数、W 总钱数）
// group[i] = 第 i 个主件组的全部合法组合 {总价, 总价值}
// 组合枚举：都不买 → 只主件 → 主+附1 → 主+附2 → 主+附1+附2
vector<vector<pair<int,int>>> groups;   // 每组若干组合
// ... 读入并枚举组合填入 groups ...

vector<int> dp(W + 1, 0);
for (auto &g : groups) {                 // 组在外
    for (int j = W; j >= 0; j--) {       // 容量倒序
        for (auto [cost, val] : g) {     // 组内组合
            if (j >= cost)
                dp[j] = max(dp[j], dp[j - cost] + val);
        }
    }
}
cout << dp[W] << endl;

和分组背包代码一模一样——区别只在"组内元素"：分组背包放单件物品，依赖背包放"组合打包件"。

---

八、变式：背包求方案数 / 恰好装满

恰好装满（初始化技巧）

普通背包 dp 全 0（允许不满）。恰好装满时：dp[0]=0，其他 dp[j]=-INF（表示"装不满"），转移时 -INF + v 保持不可达：

vector<int> dp(W+1, -1e9);
dp[0] = 0;
// 转移同上，最后 dp[W] 若仍为 -1e9 则说明装不满

求方案数（加法转移）

价值改成"方案数"，转移用 +：

vector<int> dp(W+1, 0);
dp[0] = 1;                             // 容量 0 有 1 种方案（啥都不装）
for (int i = 0; i < n; i++) {
    int w; cin >> w;                   // 只关心重量（或同时带价值）
    for (int j = W; j >= w; j--)
        dp[j] += dp[j - w];            // 加方案数
}

对比记忆：求最大价值用 max，求方案数用 +，求最小费用用 min。

---

九、终极对比表（背这张表就够了！）

| 背包类型 | 物品规则 | 遍历顺序 | dp 维度 | 关键点 |
|----------|----------|----------|:---:|--------|
| 0-1 背包 | 每件最多 1 次 | 容量倒序 | 1 维 | 一切的基础 |
| 完全背包 | 每件无限次 | 容量正序 | 1 维 | 正序=可重复 |
| 多重背包 | 每件有限 c 次 | 二进制拆分后倒序 | 1 维 | 拆成 1,2,4,... |
| 混合背包 | 三种混一起 | 按类型分方向 | 1 维 | 分类处理 |
| 二维费用 | 重量+体积双限制 | 两维都倒序 | 2 维 | 限制多一维 |
| 分组背包 | 每组最多 1 件 | 组外→容量中→物品内 | 1 维 | 组循环在最外 |
| 依赖背包 | 主件才可带附件 | 组合枚举后分组 | 1 维 | 组合当物品 |
| 恰好装满 | 初始化 -INF | 同 0-1 | 1 维 | dp[0]=0 其余 -INF |
| 求方案数 | 转移用 + | 同 0-1 | 1 维 | dp[0]=1 |

---

十、学习路线建议（按顺序吃透）

1. 0-1 背包 → P1048 采药（必做）
2. 完全背包 → P1616 疯狂的采药（必做）
3. 多重背包 → P1776 宝物筛选（二进制拆分，练手）
4. 分组背包 → P1757 通天之分组背包
5. 二维费用 → P1507 NASA的食物计划
6. 依赖背包 → P1064 金明的预算方案（有余力再看）

吃透 1~4 就够网络赛拿分了，5~6 是进阶加分项。

---

十一、自测（答得上来 = 全家桶通关）

1. 完全背包和 0-1 背包代码的唯一区别是什么？
2. 多重背包 c=13 二进制拆分成哪几个数？为什么能表示 0~13 任意数量？
3. 分组背包为什么组的循环要放最外层？
4. 恰好装满和普通背包的初始化有什么区别？
5. 二维费用背包比 0-1 多做了什么？

把答案或卡点发给我，我记录进档案并继续帮你。