第35天，动态规划part03，0-1背包问题，编程语言：C++
目录
0-1背包问题讲解——二维
0-1背包基础概念：
二维dp数组：
例题：卡码网46.携带研究材料
0-1背包问题讲解——一维
一维dp数组
例题：卡码网46.携带研究材料
416.分割集和子集
总结
0-1背包问题讲解——二维
文档讲解：代码随想录0-1背包——二维
视频讲解：手撕0-1背包问题——二维
背包问题的种类有很多，一般需要掌握的是0-1背包问题和完全背包问题。两者的区别在于：
0-1背包：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
完全背包：完全背包是从0-1背包演化而来的，与0-1背包相比，每个物品可以无限取用，求解如何装入物品能够使得价值总和最大。
因此我们先来求解0-1背包问题：
0-1背包基础概念：
对于标准的0-1背包问题，我们首先要思考如何暴力的去求解它。实际上对于每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就为O(2^n)。n表示物品的数量。暴力的解法是指数级别的时间复杂度。进而我们需要动态规划的解法来进行优化。以如下例子为例：
二维dp数组：
接下来我们从动规五部曲出发，尝试求解该问题。
1.确定dp数组以及下标的含义：我们可以通过构造一个二维dp数组来解决背包问题，其中dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。这样最后dp[n][m]就为我们要求的答案。
2. 确定递推公式：要找到递推公式，我们首先要考虑dp[i][j]能够如何得到。由于dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。因此我们可以有两个方向推出dp[i][j]。
- 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
- 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.dp数组初始化：根据递推公式，我们知道dp[i][j]是由它的上一层和左上一层推导过来的，因此第一层显然一定要进行初始化，第一层就表示取用物品0时能够得到的最大价值，因此可以通过如下代码进行初始化：
// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}
4.确定遍历顺序：可以看出背包问题是有两个遍历维度的：物品和背包的重量。那么先遍历背包还是先遍历物品呢？其实根据递归公式就可以看出，我们只需要上一层和左上层的数据，因此先遍历背包还是先遍历物品都不会影响到结果。
// weight数组的大小 就是物品个数
//先遍历物品
for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; 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]);}
}// weight数组的大小 就是物品个数
//先遍历背包
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量for(int i = 1; i < weight.size(); i++) { // 遍历物品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]);}
}5.举例推导dp数组：尝试构造一个dp数组：
例题：卡码网46.携带研究材料
题目：
代码：
#include<iostream>
using namespace std;
#include<vector>int main() {//确定研究材料种类和行李空间int M = 0;int N = 0;cin >> M;cin >> N;//构造研究材料的重量和价值vector<int> weight(M);vector<int> value(M);for(int i = 0; i < M; i++) {cin >> weight[i];}for(int i = 0; i < M; i++) {cin >> value[i];}//1.确定dp数组以及下标含义vector<vector<int>> dp(M, vector<int>(N + 1,0)); //dp[i][j]表示遍历0-i的物品，j容量能够得到的最大价值//2.确定递推公式：dp[i][j] = max(dp[i - 1][j], dp[i-1][j-weight[i]] + value[i])//3.初始化dp数组：第一列为0，第一行能够放下0号物品的为value[i]for(int i = 1; i <= N; i++) {if(i >= weight[0]) {dp[0][i] = value[0];}}//4.确定遍历顺序，先遍历物品或者先遍历背包都可以//先遍历物品for(int i = 1; i < M; i++) {for(int j = 1; j <= N; 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]);}}}cout << dp[M - 1][N];system("pause");return 0;
}
0-1背包问题讲解——一维
文档讲解：代码随想录0-1背包——一维
视频讲解：手撕0-1背包问题——一维
对于0-1背包问题，一维指的就是构造的dp数组是一维的，这样能够降低时间复杂度。一维的解法也被成为滚动数组。实质是把二维的数据进行压缩，压缩到一维上。
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，可以发现该递推公式主要依靠的就是上一层的数据，因此我们甚至可以把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
我们可以把这种拷贝用一维数组来完成。也就是只保存一层的数据并逐层更改。最终得到：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
一维dp数组
接下来我们使用动规五部曲进行分析：
1.确定dp数组的定义：一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2.一维数组的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3.一维dp数组如何初始化：首先dp[0]依照定义，表示容量0能够存储的最大价值，显然为0。其他位置可以像二维数组那样，先通过物品0进行初始化，也可以直接为0，之后我们再遍历物品0。
4.确定遍历顺序：在这里要注意，一维数组不代表我们只需要一个for循环，我们同样需要用两个for循环来遍历物品和容量。同时要注意我们需要的是上一层的数(本身）和左上原先的数(左边）因此我们这个地方需要从后往前遍历，这样才能保证后面的数取的是类似于二维数组那样，上方和左上方的数。
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]);}
}5.举例推导dp数组：
例题：卡码网46.携带研究材料
代码：
// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;int main() {// 读取 M 和 Nint M, N;cin >> M >> N;vector<int> costs(M);vector<int> values(M);for (int i = 0; i < M; i++) {cin >> costs[i];}for (int j = 0; j < M; j++) {cin >> values[j];}// 创建一个动态规划数组dp，初始值为0vector<int> dp(N + 1, 0);// 外层循环遍历每个类型的研究材料for (int i = 0; i < M; ++i) {// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for (int j = N; j >= costs[i]; --j) {// 考虑当前研究材料选择和不选择的情况，选择最大值dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);}}// 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值cout << dp[N] << endl;return 0;
}
416.分割集和子集
文档讲解：代码随想录分割集和子集
视频讲解：手撕分割集和子集
题目：
学习：本题算是子集问题的一种，可以采用回溯算法的方式进行暴力求解。但同样本题也能够转换为0-1背包问题，把给定数组看作是物品，数组中元素的值表示为物品的重量和价值（重量和价值相同），容量为我们需要的target。最后找到dp[target]的价值是否等于target就能够判断，能否拆成两个相等的子集。
代码：
//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
public:bool canPartition(vector<int>& nums) {//看作是0-1背包问题//先求和，找到targetint sum = 0;for(int i = 0; i < nums.size(); i++) {sum += nums[i];}if(sum % 2 == 1) return false; //如果为奇数肯定是不可以的int target = sum/2;//1.确定dp数组vector<int> dp(target + 1, 0);//2.确定递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])//3.初始化dp数组，全为0即可//4.确定遍历顺序for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}if (dp[target] == target) return true;return false;}
};总结
0-1背包问题，更重要的还是要理解其解题的含义，不能仅背代码，理解了dp数组的含义，才更有助于我们进行解题。
