01 背包问题是动态规划的经典模型，核心在于状态定义与转移。本文讲解如何定义二维状态 dp[i][j] 表示前 i 个物品装入容量 j 的最大价值，推导选或不选的状态转移方程。针对恰好装满的情况，通过初始化负无穷或特定标记值区分可行解。重点介绍滚动数组优化，将空间复杂度从 O(nV) 降至 O(V)，并通过逆序遍历一维数组避免状态覆盖。提供完整的 C++ 代码实现及模板。
背包问题是动态规划的一类经典问题。其本质是一种组合优化的 NP 完全问题。问题描述为：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择才能使物品的总价值最高。
根据物品个数限制，背包问题分为以下几类：
此外，根据背包是否装满可分为'不一定装满'和'一定装满'；根据限定条件个数可分为'普通背包'和'二维费用背包'。
尽管分类繁多，大多是从 01 背包演化而来，因此掌握 01 背包至关重要。背包问题的优化通常涉及空间复杂度的降低，常见方案包括滚动数组优化。
题目描述：
你有一个背包，最多能容纳的体积是 V。现在有 n 个物品，第 i 个物品的体积为 vi，价值为 wi。
输入描述：
第一行两个整数 n 和 V。接下来 n 行，每行两个数 vi 和 wi。
其中 1 ≤ n, V, vi, wi ≤ 1000。
输出描述： 输出两行，第一行为第一问答案，第二行为第二问答案（无解输出 0）。
背包问题的本质是动态规划。按照五部曲解析：
定义 dp[i][j] 表示从前 i 个物品中选择，且物品总体积不超过 j 时，能装入背包的最大物品价值。
对于第 i 个物品，有两种选择：
dp[i][j] = dp[i - 1][j]j >= v[i]）：dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i])虚拟行列初始化为 0。dp[0][j] 表示无物品，价值为 0；dp[i][0] 表示背包容量为 0，价值为 0。
从上往下，从左往右遍历。
返回 dp[n][V]。
第二问要求背包恰好装满，需在第一问基础上修改细节。
dp[i][j] 表示从前 i 个物品中选择，且物品总体积正好等于背包空间 j 时的最大价值。
判断 dp[i - 1][j - v[i]] 是否能构成 j - v[i] 的空间。设定 dp[i][j] == -1 表示无法凑成对应体积，非 -1 则为最大价值。
dp[0][0] 初始化为 0，其余 dp[0][j] 初始化为 -1，表示初始状态下只有容量 0 是可行的。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() {
int n, V;
cin >> n >> V;
// 填入题目给出的物品体积和价值的数组
for (int i = 1; i <= n; ++i) {
cin >> v[i] >> w[i];
}
// 解决第一问：求这个背包至多能装多大价值的物品
// 不需要特殊初始化，全局变量默认为 0
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= V; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
cout << dp[n][V] << endl;
// 解决第二问：若背包恰好装满，求至多能装多大价值的物品
memset(dp, 0, sizeof(dp));
// 第一行除了第一个元素之外其它元素初始化为 -1
for (int i = 1; i <= V; ++i) {
dp[0][i] = -1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= V; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i] && dp[i - 1][j - v[i]] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}
背包问题通常利用「滚动数组」进行空间优化。原二维数组 dp[i][j] 依赖 dp[i - 1][j] 和 dp[i - 1][j - v[i]]，即上一行的数据。因此可以压缩为一维数组 dp[j]。
使用一维数组时，若从左往右遍历，更新 dp[j] 时会用到已更新的 dp[j - v[i]]，这会导致当前物品被重复选取（类似完全背包）。因此，必须从右往左遍历，确保使用的是上一轮的数据。
i，只保留一维数组 dp[j]。j 的遍历顺序为从大到小（V 到 v[i]）。v[i] 即可停止。#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main() {
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; ++i) {
cin >> v[i] >> w[i];
}
// 解决第一问：求这个背包至多能装多大价值的物品
// 不需要初始化，全局变量默认为 0
for (int i = 1; i <= n; ++i) {
for (int j = V; j >= v[i]; --j) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
// 解决第二问：若背包恰好装满，求至多能装多大价值的物品
memset(dp, 0, sizeof(dp));
// 初始化除 dp[0] 外为 -1
for (int j = 1; j <= V; ++j) {
dp[j] = -1;
}
for (int i = 1; i <= n; ++i) {
for (int j = V; j >= v[i]; --j) {
if (dp[j - v[i]] != -1) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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