本文系统讲解 01 背包问题，涵盖状态定义、转移方程及二维到一维的空间优化。通过分割等和子集、目标和、最后一块石头重量 II 等经典例题，演示如何将实际问题转化为背包模型。提供 C++ 代码实现，解析逆序遍历原理，帮助读者掌握动态规划核心思想。
核心本质：你有一个容量有限的背包，面前有一堆宝物，每个宝物都有体积和价值。你的目标是：在不撑破背包的前提下，让带走的宝物总价值最高。
01 的含义：每个物品只有一件。对于每个物品，你只有两个选择：要么选 (1)，要么不选 (0)。这就是 01 背包的由来。
描述： 你有一个容量为 V 的背包，有 n 个物品。第 i 个物品体积为 v_i，价值为 w_i。 第一问：至多能装多大价值？（不一定装满） 第二问：恰好装满时，至多能装多大价值？（无解输出 0）
示例：3 件物品，容积 5。物品：(2, 10), (4, 5), (1, 4)。 第一问：14（选第 1 和第 3 件）；第二问：9（选第 2 和第 3 件）。
dp[i][j] 表示：从前 i 件物品中选，总体积不超过 j 的最大价值。
对于第 i 件物品（体积 v_i，价值 w_i），我们有两种选择：
i-1 件物品，体积不超过 j'时的价值。
dp[i][j] = dp[i-1][j]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)
#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;
}
观察方程：dp[i][j] 只依赖于上一行的 dp[i-1][...]。
如果我们去掉第一维，变成 dp[j]：
dp[j] 时，用到的 dp[j-v] 已经是本行更新过的值了（相当于物品 i 被选了多次）。dp[j] 时，j-v 在 j 的左边，还没被更新，依然是上一行的旧值。这正是我们想要的！#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;
}
描述：给你一个正整数数组，能否将其分割成两个子集，使它们的和相等？
示例：[1, 5, 11, 5] -> true (可以分成 {1, 5, 5} 和 {11})
sum / 2。sum / 2。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];
}
};
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];
}
};
描述：每个数字前加 + 或 -，凑成 target。问有多少种方法？
设加正号的数总和为 P，加负号的数总和为 M。 P - M = target，且 P + M = sum。 两式相加得：2P = sum + target ⇒ P = (sum + target) / 2。 问题转化：从数组中选出一些数，让它们的和恰好等于 P，有多少种选法？
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];
}
};
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];
}
};
描述：每次选两块石头粉碎，剩下重量差。不断重复，求最后剩下的最小重量。
我们要把石头分成两堆，让它们的重量尽可能接近 sum / 2。
这又是 01 背包：容量为 sum / 2，求能装入的最大重量。
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];
}
};
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];
}
};
核心对比卡片：
| 特性 | 朴素二维 DP | 空间优化一维 DP |
|---|---|---|
| 状态定义 | dp[i][j] (前 i 个，容量 j) | dp[j] (容量 j) |
| 空间复杂度 | O(N·V) | O(V) |
| 内层遍历顺序 | 任意（通常正序） | 必须逆序 (V → v_i) |
| 原因 | 依赖 dp[i-1][...]，行独立 | 依赖旧值，防止同层覆盖 |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online