01背包
动态规划五部曲
1、确定dp数组以及下标的含义
使用二维数组，dp[i][j]表示对于下标为0~i的物品，背包重量为j时的最大价值
背包最大重量为4
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
2、确定递推公式
- 不放物品
i，则价值和i-1的一样，所以dp[i][j] = dp[i-1][j] - 放物品
i，则背包重量要减少weight[i]，价值要增加value[i]，所以dp[i][j] = dp[i-1][j-weight[i]] + value[i]
如果放不进物品i，那只能是第一种，如果放得进，那就两种取较大值
3、dp数组初始化
第一列：首先背包重量为0时，一个物品都放不进来，所以第一列初始化为0
第一行：对于物品0，当背包重量小于物品0的重量时，都放不进来，所以初始化为0，当背包重量大于等于物品0的重量时，都放得进来，所以初始化为value[0]
剩下的初始化为0就行
4、确定遍历顺序
先遍历物品，再遍历背包，比较容易理解
也可以先遍历背包，再遍历物品，因为dp[i][j]来源于它的左上角
5、举例推导dp数组
对于物品1，背包重量为4时，可以选择不放物品1，价值不变，为15
如果选择放物品1，背包重量变为1，原先的背包重量为1的最大价值为15，再加上物品1的价值20，所以总价值为35，所以将dp[1][4]更新为35
代码
int main(int argc, char const *argv[]) {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4; // 最大背包
vector<vector<int>> dp(weight.size(), vector<int>(bagWeight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {
dp[0][j] = value[0]; // 第一行的初始化
}
for (int i = 1; i < weight.size(); i++) { // 遍历物品
for (int j = 1; j <= bagWeight; j++) { // 遍历背包
if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 放不了
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
return 0;
}
// 0 15 15 15 15
// 0 15 15 20 35
// 0 15 15 20 35 状态压缩
既然dp[i][j]只跟上一行有关，就可以只用一个滚动数组，但要注意，因为跟前面的元素有关，所以一定要先更新后面的元素，再更新前面的元素，从后往前
- 逆序遍历是为了保证每个物品只被放入一次
- 正序遍历会使得每个物品放入多次，变成完全背包
举例：物品0重量为1，价值为15
正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30这样物品0在背包2里面就放了两次
逆序遍历就不会出现这种状态的重叠
dp[2] = dp[2 - weight[0]] + value[0] = 15 // dp[1]还没更新
dp[1] = dp[1 - weight[0]] + value[0] = 15代码
int main(int argc, char const *argv[]) {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for (int i = 0; i < weight.size(); i++) { // 遍历物品
for (int j = bagWeight; j >= weight[i]; j--) { // 从后往前遍历背包，直到放不进物品i
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return 0;
}
// 0 15 15 15 15
// 0 15 15 20 35
// 0 15 15 20 35 注意：改成滚动数组之后，就必须先遍历物品，再遍历背包，不能反过来
完全背包
首先在回顾一下01背包的核心代码
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以要从小到大遍历，即：
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}既然背包变成从前往后遍历，那遍历的顺序也就没有影响了
但是如果涉及到组合与排列的问题，遍历顺序就有影响了
- 组合问题：先遍历物品，再遍历背包
- 排列问题：先遍历背包，再遍历物品
例如518-找零钱
coins={1,2}，amount=3
按组合方式遍历的dp数组为
1 1 1 1
1 1 2 2 遍历硬币1时，
dp[3]+=dp[2]=1，对应{1,1,1}遍历硬币2时，
dp[3]+=dp[1]=2，对应{1,2}
按排列方式遍历的dp数组为
1 0 0 0
1 1 0 0
1 1 2 0
1 1 2 3 遍历完硬币总值2时，dp[1]=1，dp[2]=2，dp[1]对应组成1的情况{1}，dp[2]对应组成2的情况{1,1}和{2}
当遍历到硬币总值3，硬币1时，dp[3]+=dp[2]=2，相当于在{1,1}和{2}的后面加个1，变成{1,1,1}和{2,1}
然后遍历硬币2时，dp[3]+=dp[1]=3，相当于在{1}的后面加个2，变成{1,2}
所以，3种情况是{1,1,1}，{2,1}和{1,2}
【模板】完全背包
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为$v_i$，价值为$w_i$
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入：
2 6
5 10
3 1
输出：
10
2示例2
输入：
3 8
3 10
9 1
10 1
输出：
20
0
说明：无法恰好装满背包。method
考虑能否装满，就把dp初始化为无穷小，如果j-w[i]的背包装不满，那dp[j-w[i]]+v[i]依然是一个负数，最后只要判断dp[V]是否大于0就可以知道有没有装满了
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005;
int w[N], v[N];
int dp[N];
int main() {
int n, V;
cin >> n >> V;
for (int i = 0; i < n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 0; i < n; i++) {
for (int j = w[i]; j <= V; j++) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[V] << endl;
memset(dp, -0x3f, sizeof(dp)); // 初始化为负数
dp[0] = 0; // 注意dp[0]要初始化为0
for (int i = 0; i < n; i++) {
for (int j = w[i]; j <= V; j++) { // 从前往后遍历
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
if (dp[V] > 0) cout << dp[V]; // 刚好装满
else cout << 0;
return 0;
}题型总结
