01 背包问题是动态规划经典模型，属于 NP 完全问题。核心在于定义状态 dp[i][j] 表示前 i 个物品在容量 j 下的最大价值。状态转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])。针对恰好装满的情况需初始化 dp 值为 -1。通过逆序遍历容量可将二维数组优化为一维滚动数组，将空间复杂度从 O(nV) 降至 O(V)。
背包问题是基于动态规划的一类经典组合优化 NP 完全问题。其问题描述为：给定一组物品，每种物品都有重量和价格，在限定的总重量内，如何选择才能使物品的总价格最高。
根据物品个数分类：
根据限定条件个数分类：
根据问法分类：
背包问题种类繁多，但大多从 01 背包演化而来，因此学好 01 背包至关重要。此外，背包问题的优化对时间和空间复杂度提升显著，常见优化方案包括滚动数组、单调队列优化等。
你有一个背包，最多能容纳的体积是 V。现在有 n 个物品，第 i 个物品的体积为 vi，价值为 wi。
输入描述：
第一行两个整数 n 和 V，表示物品个数和背包体积。
接下来 n 行，每行两个数 vi 和 wi，表示第 i 个物品的体积和价值。
其中 1 ≤ n, V, vi, wi ≤ 1000
输出描述： 输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出 0。
示例 1
输入：3 5
2 10
4 5
1 4
输出：14 9
说明：装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
示例 2
输入：3 8
1 2
6 11
8 6
8 8
输出：8 0
说明：装第三个物品时总价值最大但是不满，装满背包无解。
备注：要求 O(nV) 的时间复杂度，O(V) 空间复杂度。
定义 dp[i][j] 表示从前 i 个物品中选择，并且物品总体积不超过 j，此时这些选法中能装入背包的最大物品价值。
对于第 i 个物品，有两种选择：选或不选。
dp[i][j] = dp[i - 1][j]dp[i][j] = dp[i - 1][j - v[i]] + w[i] (需满足 j >= v[i])
综合：dp[i][j] = max(dp[i - 1][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]] 是否有效。设定 dp[i][j] == -1 表示无法凑到背包空间 j。
第一行除了第一个元素之外其它元素初始化为 -1，表示无法装满。
#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;
// 填入题目给出的物品体积和价值的数组 -- 从下标为 1 开始
for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
// 解决第一问：求这个背包至多能装多大价值的物品
// 不需要初始化
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));
// 先清空 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 - 1][j] 和 dp[i - 1][j - v[i]]，即上一行的数据。因此可以将二维数组压缩为一维数组。
关键在于遍历顺序。如果使用一维数组 dp[j]，当计算 dp[j] 时需要用到 dp[j - v[i]]。如果从左往右遍历，dp[j - v[i]] 可能已经被当前轮次更新过，导致重复使用同一物品。因此必须从右往左遍历容量 j。
优化操作总结：
i）。j 的遍历顺序（从 V 到 v[i] 逆序）。空间优化后，空间复杂度从 O(nV) 降至 O(V)。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N]; // 只需要一维 dp 数组
int main() {
int n, V;
cin >> n >> V;
// 填入题目给出的物品体积和价值的数组 -- 从下标为 1 开始
for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
// 解决第一问：求这个背包至多能装多大价值的物品
// 不需要初始化
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 表
// 第一行除了第一个元素之外其它元素初始化为 -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