背包问题概述
背包问题是基于动态规划的一类经典组合优化 NP 完全问题。其问题描述为:给定一组物品,每种物品都有重量和价格,在限定的总重量内,如何选择才能使物品的总价格最高。
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