问题描述
01背包问题
有\(N\)件物品和一个容量是\(V\)的背包，每件物品只能使用一次。
第\(i\)件物品的体积是\(v_i\)，价值是\(w_i\)，求解将哪些物品装入背包，可使这些物品总体积不超过背包容量，并且总价值最大。
解题思路
动态规划的经典例题，首先考虑dp[i][j]的含义，这里i表示只考虑前i个物品(i从\(1\sim N\))，dp[i][j]表示总体积为j的情况下，考虑前i个物品时，背包里的物品的最大价值。
可以分成两种情况考虑dp[i][j]的递推关系：
- 第
i个物品不在背包中时，dp[i][j] = dp[i - 1][j]- 此时只有前
i - 1个物品，背包中物品体积仍为j。
- 此时只有前
- 第
i个物品在背包中时，dp[i][j] = dp[i - 1][j - v[i]] + w[i]- 前
i - 1个物品的体积为j - v[i]。
- 前
初始化，显然dp[0][0] = 0。
根据递推关系和初始化条件写for循环遍历即可。
代码
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = 1010; // 体积不超过1000， 物品件数也不超过1000
int main() {
int n, m; // n为物品数量，m为背包体积
cin >> n >> m;
int dp[N][N] = {0};
int v[N] = {0}; // 体积
int w[N] = {0}; // 价值
for (int i = 1; i <=n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i]) // 当前总体积肯定不能小于v[i]，如果小于的话，第i个物品不能放
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
// int res = 0;
// for (int j = 1; j <=m; j++) {
// res = max(res, dp[n][j]); // 不需要遍历，直接输出dp[n][m]即可
// }
cout << dp[n][m] << endl;
return 0;
}
优化
分析上面的代码，实际上dp[i][j]递推时只会用到dp[i - 1][j]，而不会用到dp[i - 2][j], dp[i - 3][j]等，因此dp数组实际上只需要一维即可，索引为当前总体积。
那么，是否可以直接写成
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++)
if (j >= v[i])
// 这里的max实际上是
// max(dp[i][j], dp[i][j - v[i]] + w[i])
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
不可以！原因已在上面的代码里的注释中给出，应该是max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])才对。
正确的写法应该是:
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--)
// 因为dp[j], dp[j - v[i]]只在上一次的i循环中才被赋值了，
// 所以这里用的实际上是dp[i - 1][j - v[i]]
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
如果dp[0] = 0， dp[i] = -INF，那么状态只能从dp[0]转移过来，可以求解总体积恰为\(V\)的情况。
优化后的完整代码：
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = 1010; // 体积不超过1000， 物品件数也不超过1000
int main() {
int n, m; // n为物品数量，m为背包体积
cin >> n >> m;
int dp[N] = {0};
int v[N] = {0}; // 体积
int w[N] = {0}; // 价值
for (int i = 1; i <=n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
// 当前总体积肯定不能小于v[i]，如果小于的话，第i个物品不能放
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
// int res = 0;
// for (int j = 1; j <=m; j++) {
// res = max(res, dp[n][j]); // 不需要遍历，直接输出dp[n][m]即可
// }
cout << dp[m] << endl;
return 0;
}