一、前言：什么是背包问题？
核心本质：你有一个容量有限的背包，面前有一堆宝物，每个宝物都有体积和价值。你的目标是：在不撑破背包的前提下，让带走的宝物总价值最高。
01 的含义：每个物品只有一件。对于每个物品，你只有两个选择：要么选 (1)，要么不选 (0)。这就是 01 背包的由来。
二、01 背包：标准模板与两种形态
2.1 题目描述
描述： 你有一个容量为 V 的背包，有 n 个物品。第 i 个物品体积为 v_i，价值为 w_i。 第一问：至多能装多大价值？（不一定装满） 第二问：恰好装满时，至多能装多大价值？（无解输出 0）
示例：3 件物品，容积 5。物品：(2, 10), (4, 5), (1, 4)。 第一问：14（选第 1 和第 3 件）；第二问：9（选第 2 和第 3 件）。
2.2 深度拆解（第一问：不超过 V）
1. 状态表示
dp[i][j] 表示：从前 i 件物品中选，总体积不超过 j 的最大价值。
2. 状态转移方程
对于第 i 件物品（体积 v_i，价值 w_i），我们有两种选择：
- 不选它：最大价值等于'前
i-1件物品，体积不超过j'时的价值。dp[i][j] = dp[i-1][j] - 选它：前提是背包得装得下（j >= v_i）。最大价值等于'第
i件的价值'加上'前i-1件物品，剩余空间 j - v_i'时的最大价值。dp[i][j] = dp[i-1][j - v_i] + w_i
综合方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - v_i] + w_i)
3. 朴素二维代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int dp[N][N]; // 二维数组
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
// 第一问：不超过 V
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
// 1. 不选第 i 个
dp[i][j] = dp[i-1][j];
// 2. 选第 i 个 (前提是装得下)
if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
// 第二问：恰好装满 V
// 初始化：dp[0][0] = 0, 其余为 -INF (表示不可能)
for (int j = 0; j <= V; j++) dp[0][j] = -0x3f3f3f3f;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i-1][j];
if (j >= v[i] && dp[i-1][j - v[i]] != -0x3f3f3f3f) // 只有前一个状态合法才能转移
dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
}
}
// 如果 dp[n][V] 还是负数，说明无解，输出 0
cout << (dp[n][V] < 0 ? 0 : dp[n][V]) << endl;
return 0;
}
2.3 进阶：空间优化（滚动数组）
1. 为什么要逆序？
观察方程：dp[i][j] 只依赖于上一行的 dp[i-1][...]。
如果我们去掉第一维，变成 dp[j]：
- 正序遍历：计算
dp[j]时，用到的dp[j-v]已经是本行更新过的值了（相当于物品 i 被选了多次）。 - 逆序遍历：计算
dp[j]时，j-v 在 j 的左边，还没被更新，依然是上一行的旧值。这正是我们想要的！
2. 优化后的一维代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int dp[N]; // 一维数组
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
// 第一问：不超过 V
for (int i = 1; i <= n; i++) {
// 逆序遍历！从 V 到 v[i]
for (int j = V; j >= v[i]; j--) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
// 第二问：恰好装满 V
// 初始化：只有容量为 0 时价值为 0，其余为 -INF
for (int j = 1; j <= V; j++) dp[j] = -0x3f3f3f3f;
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j--) {
if (dp[j - v[i]] != -0x3f3f3f3f) // 只有前置状态有效才更新
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
return 0;
}
三、分割等和子集：决策类背包
3.1 题目解析
描述：给你一个正整数数组，能否将其分割成两个子集，使它们的和相等？
示例：[1, 5, 11, 5] -> true (可以分成 {1, 5, 5} 和 {11})
3.2 思路转换
- 转化：这道题等价于——能否从数组中选出一些数，让它们的和恰好等于
sum / 2。 - 映射到背包：
- 背包容量：
sum / 2。 - 物品：数组里的每个数（体积和价值都是数值本身）。
- 目标：能否装满？
- 背包容量：
3.3 朴素二维代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int x : nums) sum += x;
if (sum % 2 != 0) return false; // 奇数分不了
int target = sum / 2;
int n = nums.size();
// dp[i][j] 表示前 i 个数能否凑成和 j
vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
// 初始化：凑成和为 0，不需要选任何数，天然为 true
for (int i = 0; i <= n; i++) dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
// 不选第 i 个数
dp[i][j] = dp[i-1][j];
// 选第 i 个数
if (j >= nums[i-1]) {
dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
}
}
}
return dp[n][target];
}
};
3.4 空间优化代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int x : nums) sum += x;
if (sum % 2 != 0) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true; // 初始化
for (int x : nums) {
// 逆序遍历，防止重复选择同一个数
for (int j = target; j >= x; j--) {
dp[j] = dp[j] || dp[j - x];
}
}
return dp[target];
}
};
四、目标和：求方案数
4.1 题目解析
描述：每个数字前加 + 或 -，凑成 target。问有多少种方法？
4.2 思路转换
设加正号的数总和为 P，加负号的数总和为 M。 P - M = target，且 P + M = sum。 两式相加得：2P = sum + target ⇒ P = (sum + target) / 2。 问题转化：从数组中选出一些数，让它们的和恰好等于 P，有多少种选法？
4.3 朴素二维代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int x : nums) sum += x;
if (abs(target) > sum || (sum + target) % 2 != 0) return 0;
int bagSize = (sum + target) / 2;
int n = nums.size();
// dp[i][j] 前 i 个数凑成和 j 的方案数
vector<vector<int>> dp(n + 1, vector<int>(bagSize + 1, 0));
dp[0][0] = 1; // 凑成 0 的方案数为 1 (空集)
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= bagSize; j++) {
// 不选
dp[i][j] = dp[i-1][j];
// 选
if (j >= nums[i-1]) {
dp[i][j] += dp[i-1][j - nums[i-1]];
}
}
}
return dp[n][bagSize];
}
};
4.4 空间优化代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int x : nums) sum += x;
if (abs(target) > sum || (sum + target) % 2 != 0) return 0;
int bagSize = (sum + target) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int x : nums) {
// 逆序遍历
for (int j = bagSize; j >= x; j--) {
dp[j] += dp[j - x];
}
}
return dp[bagSize];
}
};
五、最后一块石头的重量 II：最小差值
5.1 题目解析
描述：每次选两块石头粉碎，剩下重量差。不断重复，求最后剩下的最小重量。
5.2 思路转换
我们要把石头分成两堆，让它们的重量尽可能接近 sum / 2。
这又是 01 背包：容量为 sum / 2，求能装入的最大重量。
5.3 朴素二维代码
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for (int x : stones) sum += x;
int target = sum / 2;
int n = stones.size();
// dp[i][j] 前 i 个石头，容量 j，最大重量
vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i-1][j];
if (j >= stones[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - stones[i-1]] + stones[i-1]);
}
}
}
return sum - 2 * dp[n][target];
}
};
5.4 空间优化代码
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for (int x : stones) sum += x;
int target = sum / 2;
vector<int> dp(target + 1, 0);
for (int x : stones) {
// 逆序遍历
for (int j = target; j >= x; j--) {
dp[j] = max(dp[j], dp[j - x] + x);
}
}
return sum - 2 * dp[target];
}
};
六、总结：01 背包的灵魂
核心对比卡片：
| 特性 | 朴素二维 DP | 空间优化一维 DP |
|---|---|---|
| 状态定义 | dp[i][j] (前 i 个，容量 j) | dp[j] (容量 j) |
| 空间复杂度 | O(N·V) | O(V) |
| 内层遍历顺序 | 任意（通常正序） | 必须逆序 (V → v_i) |
| 原因 | 依赖 dp[i-1][...]，行独立 | 依赖旧值，防止同层覆盖 |
