背包问题族

前言

上一篇 DP 入门 建立了”状态 + 转移”的框架。这一篇聚焦 DP 最经典的模型——背包问题。

场景很简单：你有一个容量有限的背包，面前有很多物品，每个有重量和价值。你想在不超过背包容量的前提下，使选中物品的总价值最大。

听起来朴素，但这个模型极其强大。“去不去旅行”是 0-1 背包（每件事要么做要么不做），“零钱兑换”是完全背包（每种硬币可以用无限次），“分组背包”是加了约束的变种。掌握了背包，你就掌握了 DP 最重要的一类状态设计。

问题的本质

0-1 背包的核心矛盾

每件物品要么选，要么不选——没有”选一半”这种操作。暴力枚举 $2^N$ 种方案不可行。

DP 的关键观察：如果我已经决定了前 $i-1$ 件物品怎么选，第 $i$ 件物品只有两种可能——选或不选。我只需要知道”用了多少容量”就足够了，不需要知道具体选了哪些物品。

这就是状态设计：$dp[j]$ = 容量恰好为 $j$ 时能获得的最大价值。

循环方向的秘密

0-1 背包内层循环 $j$ 必须从大到小。为什么？

考虑当前处理物品 $i$（重量 $w$，价值 $v$）。如果 $j$ 从小到大遍历：

j = w:   dp[w]  = max(dp[w], dp[0] + v)     ← 用了 dp[0]
j = 2w:  dp[2w] = max(dp[2w], dp[w] + v)    ← 但 dp[w] 刚被更新过！

这意味着物品 $i$ 被选了两次——违反了”每件只能选一次”的规则。

从大到小就没这个问题：

j = 2w:  dp[2w] = max(dp[2w], dp[w] + v)    ← dp[w] 还是旧值
j = w:   dp[w]  = max(dp[w], dp[0] + v)     ← 现在才更新 dp[w]

物品 $i$ 每个容量只被考虑一次。✓

完全背包恰恰相反——每件物品可以选无限次，所以 $j$ 从小到大，允许同一物品被多次使用。

当 $W$ 太大时：互换重量和价值

标准的 0-1 背包时间 $O(NW)$，但如果 $W = 10^9$，直接做会 TLE。

关键技巧：如果价值 $v_i$ 很小（比如 $\le 1000$），那就把状态定义换过来——$dp[j]$ = 达到总价值 $j$ 所需的最小重量。 这样状态数从 $W$ 变成 $N \times v_{\max}$。

理论 + 代码

0-1 背包（标准版）

状态：$dp[j]$ = 容量 $j$ 下的最大价值。

转移：$dp[j] = \max(dp[j],\ dp[j - w_i] + v_i)$，$j$ 从 $W$ 到 $w_i$ 倒序。

long long dp[100006]; // dp[j] = 容量 j 时的最大价值

for (int i = 1; i <= N; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // ① 选 or 不选

逐行解析：

• ① 对于容量 $j$，要么不选物品 $i$（保持 $dp[j]$），要么选（$dp[j-w_i]+v_i$）。取较大值。
• $j$ 从 $W$ 到 $w_i$ 倒序，保证每件物品只被考虑一次。

模拟：$N=3, W=8$，物品 $(3,30), (4,50), (5,60)$。

阶段	dp[0]	dp[3]	dp[4]	dp[5]	dp[7]	dp[8]
初始	0	0	0	0	0	0
物品1(w=3,v=30)	0	30	0	0	0	0
物品2(w=4,v=50)	0	30	50	50	80	80
物品3(w=5,v=60)	0	30	50	60	80	90

$dp[8] = 90$，对应选物品 1 和 3（$3+5=8$, $30+60=90$）。✓

0-1 背包（$W$ 很大时）

状态：$dp[j]$ = 达到总价值 $j$ 所需的最小重量。

转移：$dp[j] = \min(dp[j],\ dp[j - v_i] + w_i)$。

答案：最大的 $j$ 使得 $dp[j] \le W$。

long long dp[100009]; // dp[j] = 价值 j 时的最小重量
// 初始化：dp[0] = 0, 其余 = INF

for (int i = 1; i <= N; i++)
    for (int j = Vmax; j >= v[i]; j--)
        dp[j] = min(dp[j], dp[j - v[i]] + w[i]); // ① 互换！

// ② 找最大的 j 使得 dp[j] <= W
long long ans = 0;
for (int j = 0; j <= Vmax; j++)
    if (dp[j] <= W) ans = j;

• ① 和标准 0-1 背包结构完全一样，只是把 $w$ 和 $v$ 互换了。
• ② 答案不再是 $dp[W]$，而是遍历所有可能的价值 $j$，找最大的满足重量约束的。

例题

例题 1：M&A 030 — Knapsack 1

题目：$N$ 个物品，重量 $w_i$，价值 $v_i$，背包容量 $W$。求最大总价值。

数据范围：$1 \le N \le 100$，$1 \le W \le 10^5$，$1 \le v_i \le 10^9$

—— AtCoder M&A 030

分析：标准 0-1 背包。$W \le 10^5$，用 $O(NW)$ 的标准做法。注意 $v_i$ 最大 $10^9$，答案要用 long long。

输入样例：

3 8
3 30
4 50
5 60

输出：90

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

long long dp[100006];

int main() {
    int N, W;
    scanf("%d%d", &N, &W);
    for (int i = 0; i < N; i++) {
        int w, v;
        scanf("%d%d", &w, &v);
        for (int j = W; j >= w; j--)           // ① 倒序！
            dp[j] = max(dp[j], dp[j - w] + v); // ② 选 or 不选
    }
    printf("%lld\n", dp[W]);
}

逐行解析：

• ① $j$ 从 $W$ 到 $w$ 倒序，保证每件物品只被选一次。
• ② $dp[j-w]+v$ 表示”如果选了当前物品，从剩余容量 $j-w$ 的最优解加上当前价值”。

---

例题 2：TB B19 — Knapsack 2（$W$ 很大）

题目：$N$ 个物品，重量 $w_i$，价值 $v_i$，背包容量 $W$。求最大总价值。

数据范围：$1 \le N \le 100$，$1 \le W \le 10^9$，$1 \le v_i \le 1000$

—— AtCoder Tessoku Book B19

分析：$W = 10^9$，标准 $O(NW)$ 不可行。但 $v_i \le 1000$，所以总价值最多 $N \times 1000 = 10^5$。互换重量和价值——$dp[j]$ = 达到价值 $j$ 所需的最小重量。

教材 4.4 节专门讲解了这个技巧。

输入样例：

4 7
3 13
3 17
5 29
1 10

输出：40

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const long long INF = 1e18;
long long dp[100009]; // dp[j] = 价值 j 时的最小重量

int main() {
    int N, W;
    scanf("%d%d", &N, &W);
    int w[109], v[109];
    for (int i = 1; i <= N; i++) scanf("%d%d", &w[i], &v[i]);

    // ① 初始化
    for (int j = 0; j <= 100000; j++) dp[j] = INF;
    dp[0] = 0;                                     // 价值 0 不需要任何重量

    // ② DP
    for (int i = 1; i <= N; i++)
        for (int j = 100000; j >= v[i]; j--)
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]); // ③ 互换！

    // ④ 找答案
    long long ans = 0;
    for (int j = 0; j <= 100000; j++)
        if (dp[j] <= W) ans = j;                    // ⑤ 满足容量约束的最大价值
    printf("%lld\n", ans);
}

逐行解析：

• ① $dp[0]=0$（价值 0 不需要重量），其余初始化为 INF（不可达）。
• ③ 和标准 0-1 背包结构一样，但 $w$ 和 $v$ 互换了位置。
• ⑤ 遍历所有价值，找满足 $dp[j] \le W$ 的最大 $j$。

模拟：样例 1，$N=4, W=7$，物品 $(3,13), (3,17), (5,29), (1,10)$。总价值上限 = $13+17+29+10=69$。

物品 1 后：$dp[13]=3$。 物品 2 后：$dp[17]=3$，$dp[30]=6$。 物品 3 后：$dp[29]=5$，$dp[42]=8$，$dp[46]=8$，$dp[59]=11$。 物品 4 后：$dp[10]=1$，$dp[23]=4$，$dp[27]=4$，$dp[30]=\min(6, 4)=4$，$dp[40]=\min(7, 6)=6$ …

最大 $j$ 使得 $dp[j] \le 7$：$j=40$ 时 $dp[40]=6 \le 7$。✓

---

例题 3：M&A 096 — Cooking（双炉灶调度）

题目：$N$ 道菜，第 $i$ 道需要时间 $T_i$。两个炉灶同时工作，每道菜只能在一个炉灶上做。求做完所有菜的最短时间。

数据范围：$1 \le N \le 100$，$1 \le T_i \le 10^3$

—— AtCoder M&A 096

分析：两个炉灶，每道菜分配到其中一个。总时间 = 两个炉灶中较大的那个完成时间。我们希望这个最大值尽可能小。

设总时间 $S = \sum T_i$。如果炉灶 A 的工作时间为 $j$，那炉灶 B 的时间是 $S - j$。总时间 = $\max(j, S-j)$。要让这个值最小，$j$ 应尽量接近 $S/2$。

所以问题转化成：从 $N$ 个数中选一些，使它们的和尽可能接近 $S/2$。这就是一个子集和问题——0-1 背包的判定版本。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int T[109], S = 0;
    for (int i = 0; i < N; i++) { scanf("%d", &T[i]); S += T[i]; }

    bool dp[100009] = {};
    dp[0] = true;                                   // ① 和为 0 恒可达
    for (int i = 0; i < N; i++)
        for (int j = S; j >= T[i]; j--)
            dp[j] = dp[j] || dp[j - T[i]];          // ② bool 版 0-1 背包

    int ans = S;
    for (int j = 0; j <= S; j++)
        if (dp[j]) ans = min(ans, max(j, S - j));   // ③ 取最优分割
    printf("%d\n", ans);
}

逐行解析：

• ① $dp[0] = true$：不选任何数，和为 0。
• ② 标准的 0-1 背包转移，但不需要记录价值，只记录”和为 $j$ 是否可达”。
• ③ 枚举所有可达的和 $j$，炉灶 A 用 $j$，炉灶 B 用 $S-j$，取两者最大值的最小值。

---

例题 4：TB A18 — Subset Sum（子集和判定）

题目：$N$ 个正整数 $A_1, \ldots, A_N$，目标 $S$。能否从中选一些使和恰好为 $S$？如果能，输出方案。

数据范围：$1 \le N \le 60$，$1 \le S \le 10000$

—— AtCoder Tessoku Book A18

分析：0-1 背包的判定版本。$dp[i][j]$ = 考虑前 $i$ 个数，和为 $j$ 是否可达。如果还要还原方案，需要额外记录”选择了哪个”。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool dp[69][10009]; // dp[i][j] = 前 i 个数中和 j 是否可达

int main() {
    int N, S;
    scanf("%d%d", &N, &S);
    int A[69];
    for (int i = 1; i <= N; i++) scanf("%d", &A[i]);

    dp[0][0] = true;                                // ① 初始
    for (int i = 1; i <= N; i++)
        for (int j = 0; j <= S; j++) {
            if (j < A[i]) dp[i][j] = dp[i-1][j];           // ② 不够选
            else dp[i][j] = dp[i-1][j] || dp[i-1][j-A[i]]; // ③ 选 or 不选
        }

    if (!dp[N][S]) { printf("-1\n"); return 0; }

    // ④ 路径还原
    vector<int> ans;
    int pos = S;
    for (int i = N; i >= 1; i--) {
        if (dp[i-1][pos]) continue;                 // ⑤ 不选 i
        ans.push_back(i);
        pos -= A[i];                                // ⑥ 选了 i
    }
    reverse(ans.begin(), ans.end());
    printf("%d\n", (int)ans.size());
    for (int i = 0; i < (int)ans.size(); i++) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}

逐行解析：

• ②③ 转移：要么不选 $A_i$（$dp[i-1][j]$），要么选（$dp[i-1][j-A_i]$），任一可达即可。
• ⑤⑥ 从终点 $S$ 倒推：如果 $dp[i-1][pos]$ 为 true，说明不选 $A_i$ 也能达到 $pos$；否则一定选了 $A_i$，$pos$ 减去 $A_i$。

模拟：$N=5, S=9, A=[2, 2, 3, 5, 5]$。

i\j	0	2	3	4	5	6	7	8	9
0	T
1(2)	T	T
2(2)	T	T		T
3(3)	T	T	T	T	T	T
4(5)	T	T	T	T	T	T	T	T	T

$dp[4][9] = true$，还原路径：$9-5=4, 4-2=2, 2-2=0$。选了 1,2,4。✓

---

例题 5：T90 037 — Don’t Leave the Spice（★5，区间背包）

题目：$N$ 种料理，料理 $i$ 的价值 $V_i$，消耗香料 $[L_i, R_i]$（可以选择范围内任意量）。能否恰好消耗 $W$ 香料？如果能，求最大总价值。

数据范围：$1 \le W \le 10^4$，$1 \le N \le 500$

—— AtCoder Typical 90 037

分析：这是 0-1 背包的变体——每件物品的重量不是固定值，而是一个区间 $[L_i, R_i]$。对于每个容量 $j$，物品 $i$ 可以贡献 $[L_i, R_i]$ 中的任意值。

状态还是 $dp[j]$ = 消耗恰好 $j$ 香料时的最大价值。转移时，需要从 $dp[j-k]$ 转移过来，其中 $L_i \le k \le R_i$。

朴素做法对每个 $j$ 枚举 $k$，$O(N \times W \times R)$ 会超时。用**滑动窗口最大值（单调队列）**优化：对于固定的物品 $i$，按 $j \bmod L_i$ 分组，每组内用单调队列维护窗口 $[j-R_i, j-L_i]$ 中的最大值。

但更简单的做法是：$O(N \times W \times (R_i - L_i))$ 在本题数据范围内可以接受（$N=500, W=10^4, R-L$ 平均较小）。

代码（朴素版本）：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1e18;
long long dp[10009], ndp[10009];

int main() {
    int W, N;
    scanf("%d%d", &W, &N);
    int L[509], R[509], V[509];
    for (int i = 1; i <= N; i++) scanf("%d%d%d", &L[i], &R[i], &V[i]);

    for (int j = 0; j <= W; j++) dp[j] = -INF;
    dp[0] = 0;                                       // ① 消耗 0 香料，价值 0

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) ndp[j] = dp[j]; // ② 不选料理 i
        for (int j = L[i]; j <= W; j++) {
            // ③ 枚举选了料理 i，消耗 k 香料
            for (int k = L[i]; k <= R[i] && j - k >= 0; k++) {
                if (dp[j - k] >= 0)
                    ndp[j] = max(ndp[j], dp[j - k] + V[i]);
            }
        }
        memcpy(dp, ndp, sizeof(dp));
    }

    printf("%lld\n", dp[W] >= 0 ? dp[W] : -1);       // ④ 判断是否可达
}

逐行解析：

• ① $dp[0]=0$：消耗 0 香料的价值是 0，其他状态不可达。
• ② ndp[j] = dp[j]：不选料理 $i$ 的方案，价值不变。
• ③ 选料理 $i$，消耗 $k \in [L_i, R_i]$ 香料，从 $dp[j-k]$ 转移。
• ④ 如果 $dp[W] < 0$，说明恰好消耗 $W$ 香料不可行，输出 -1。

模拟：$W=100, N=4$，料理 $(30,40,120), (30,40,30), (30,40,1500), (30,40,40)$。

选料理 1,3,4，各消耗 $100/3 \approx 33$（在 $[30,40]$ 内），总价值 $120+1500+40=1660$。✓

参考文献

教材讲解 — 競技プログラミングの鉄則 第 4 章

• 4.3 B18 Subset Sum（子集和判定 解说）
• 4.4 B19 Knapsack 2（重量/价值互换 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 030 Knapsack 1（标准 0-1 背包）【例题】
• 096 Cooking（子集和分割）【例题】

系统练习 — 競技プログラミングの鉄則

• A18 Subset Sum（子集和判定+还原）【例题】
• A19 Knapsack 1（标准 0-1 背包）
• B18 Subset Sum with Restoration（子集和还原）
• B19 Knapsack 2（价值互换 $W \le 10^9$）【例题】

实战练习 — 競プロ典型 90 問

• 037 Don’t Leave the Spice（★5，区间背包）【例题】
• 056 Lucky Bag（★5，完全背包/概率）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化