问题概述
背包问题（Knapsack Problem）源于一个经典场景：背包容量有限，每个物品有自己的重量和价值，目标是在不超过背包容量的前提下，使总价值最大。根据物品的选取规则，主要分为三类：
- 01 背包：每个物品最多选一次；
- 完全背包：每个物品可以选任意多次；
- 多重背包：每个物品有固定的数量上限。
01 背包
状态定义与转移
定义 dp[i][j] 为”前 i 个物品、容量为 j 时能获得的最大价值”。对第 i 个物品只有两种选择：
- 不选：
dp[i][j] = dp[i-1][j]； - 选（要求
j ≥ w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
C++ 实现（二维）
int knapsack01(int W, const vector<int>& weights, const vector<int>& values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j < weights[i-1]) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
}
}
return dp[n][W];
}
空间优化（一维滚动数组）
观察转移方程，dp[i] 只依赖 dp[i-1]，可以压成一维。关键：内层容量循环必须从大到小（j 从 W 递减），保证每个物品只被使用一次——如果从小到大，dp[j-w[i]] 可能已经被本轮物品更新过，等于允许了重复选取。
int knapsack01_opt(int W, const vector<int>& weights, const vector<int>& values) {
int n = weights.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = W; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
完全背包
每种物品无限量。转移方程与 01 背包的唯一区别是：选中物品后从 dp[i][j-w[i]] 转移（允许在本轮继续使用该物品），而不是 dp[i-1][j-w[i]]：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
对应的一维优化恰好相反——内层容量循环从小到大，这样 dp[j-w[i]] 可能是本轮已经更新的值，天然实现了”可以重复选”：
int knapsackComplete(int W, const vector<int>& weights, const vector<int>& values) {
int n = weights.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = weights[i]; j <= W; j++) {
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
多重背包
每种物品有数量限制 s[i]。朴素做法是三重循环（枚举物品、容量、个数）：
for (int i = 1; i <= n; i++) // 物品
for (int j = V; j >= 0; j--) // 容量
for (int k = 1; k <= s[i] && k*w[i] <= j; k++) // 数量
dp[j] = max(dp[j], dp[j - k*w[i]] + k*v[i]);
复杂度 O(n·V·s)，s 很大时会超时。
二进制优化
把第 i 种物品按 1、2、4、…、2^k、剩余部分拆分成若干”新物品”，每个新物品重量为 k·w[i]、价值为 k·v[i]，用 01 背包处理。任何 0..s[i] 的数量都可以由这些二进制分组组合出来，物品总数从 s[i] 降到 O(log s[i])，复杂度变为 O(n·V·log s)：
vector<pair<int,int>> items;
for (int i = 1; i <= n; i++) {
int cnt = s[i];
for (int k = 1; k <= cnt; k <<= 1) {
items.push_back({k*w[i], k*v[i]});
cnt -= k;
}
if (cnt > 0) items.push_back({cnt*w[i], cnt*v[i]});
}
for (auto& it : items) // 01 背包
for (int j = V; j >= it.first; j--)
dp[j] = max(dp[j], dp[j - it.first] + it.second);
分组背包
物品分成若干组，每组最多选一个。枚举组 → 容量 → 组内物品：
int groupKnapsack(int V, vector<vector<pair<int,int>>>& groups) {
vector<int> dp(V + 1, 0);
for (auto& group : groups) { // 组
for (int j = V; j >= 0; j--) { // 容量（倒序，保证每组最多选一个）
for (auto& [w, v] : group) {
if (j >= w) dp[j] = max(dp[j], dp[j - w] + v);
}
}
}
return dp[V];
}
总结与要点
| 类型 | 转移来源 | 一维循环方向 | 复杂度 |
|---|---|---|---|
| 01 背包 | dp[i-1][j-w] | 容量倒序 | O(nV) |
| 完全背包 | dp[i][j-w] | 容量正序 | O(nV) |
| 多重背包 | 01 背包拆分 | 容量倒序 | O(nV·log s) |
| 分组背包 | 组内 01 背包 | 容量倒序 | O(nV) |
核心记忆点：循环方向决定”能否重复选”——倒序是 01（每个物品一次），正序是完全（无限次）。面试和竞赛里所有背包变种几乎都能归约到这几种基本形态。