代码随想录算法训练营第四十二天| 01背包问题二维，01背包问题一维，416. 分割等和子集

题目链接： 01背包问题二维

思路

代码

题目链接：01背包问题一维

思路

代码

题目链接： 416. 分割等和子集

思路

代码

总结

题目链接：01背包问题二维

思路

①dp数组，物品从下标0到i的物品中任取，然后放进容量为j的背包里，此时最大的价值

②递推公式，到第i个物品时有两个选择，放或者不放。如果不放，最大价值就是dp[i-1][j]，说明第i个物品太大了放不下，价值还是和i-1的状态一样；如果放，最大价值就是i-1时的价值加上value[i]，即dp[i-1][j-wight[i]]+value[i]。也就是说当前dp[i][j]可以由这两个状态推导而来，因为要取最大价值，所以取这两个值中的最大值

③dp数组初始化，由递推公式可知，dp数组当前值可由左上角和正上方两个方向推导而来，所以只需要初始化第一列和第一行即可由递推公式得到整个二维dp数组。当背包容量为0时，放不了东西，所以这一列初始化为0；下标为物品0时，如果背包容量足够就将其初始化为物品0的价值，如果放不下就初始化为0

④遍历顺序，由递推公式可知，只要有左上角和上方的值即可推导当前值，所以先遍历行或者列，或者说先遍历物品或者背包都可以

⑤推导dp数组

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int m,n;//m为物品个数，n为背包空间
void solve(){vector<int> weight(m,0);//物品重量vector<int> value(m,0);//物品价值vector<vector<int>> dp(m,vector<int>(n+1,0));//dp数组//输入重量和价值for(int i = 0; i < m; i++){cin>>weight[i];}for(int i = 0; i < m; i++){cin>>value[i];}//当第一个物品的重量小于背包空间时//此时dp赋值为该物品的valuefor(int j = weight[0]; j <= n; j++){dp[0][j] = value[0];}//遍历背包for(int j = 0; j <= n; j++){//遍历物品，物品从1到ifor(int i = 1; i < m; i++){if(weight[i] > j) //装不下时，价值与遍历到上一个物品时一样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]<<endl;}int main(){while(cin>>m>>n){solve();}return 0;
}

题目链接：01背包问题一维

思路

①dp数组，容量为j的背包，能装的物品价值最大为dp[j]

②递推公式，与二维类似，只不过用了一维的滚动数组。此时背包空间为j，有两个选择：装不下当前物品，则此时背包的价值与遍历上一个物品时一样，也就是dp[j] = dp[j-weight[i]]；能装下时，有两种情况，装完后价值比之前大，装完后价值比之前小，肯定是二者选最大。装之前，dp[j] = dp[j-weight[i]]，装之后，dp[j] = dp[j-weight[i]] + value[i]。

③dp数组初始化，根据递推公式可知背包空间为0时装不了物品，所以价值为0即dp[0] = 0，往后遍历时会进行更新，所以其他位置先初始化为0即可。

④遍历顺序，先物品，后背包，且背包倒序遍历，从空间最大往前遍历。因为是先遍历物品，如果背包正序遍历，则物品i可能会被重复放入。

⑤推导dp数组

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;//一维dp数组
int m,n;//m为物品种类，n为背包容量
void solve(){vector<int> weight(m,0);vector<int> value(m,0);//dp[n]的意义是背包容量为n的时候，所装物品的最大价值为dp[n]//因为dp数组从0开始，所以dp数组的大小为n+1vector<int> dp(n+1,0);//输入物品信息，重量和价值for(int i = 0; i < m; i++){cin>>weight[i];}for(int i = 0; i < m; i++){cin>>value[i];}//遍历顺序，先物品，后背包，其背包倒序遍历//由于dp数组大小有限，并不会保存上一层的信息//所以要先遍历物品，把当前物品处理完再进行下一层//背包倒序遍历是防止同一物品被多次装入背包for(int i = 0; i < m; i++){//如果能装下才对dp数组当前位置进行更新for(int j = n; j >=weight[i]; j--){dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);}}cout<<dp[n]<<endl;
}int main(){while(cin>>m>>n){solve();}return 0;
}

题目链接：416. 分割等和子集

思路

将该题归类为01背包问题

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

①dp数组，容量为j的背包所装物品的最大价值为dp[j]，本题所给的数组既是重量也是价值

②递推公式，dp[j] = max[dp[j], dp[j-nums[i]]+nums[i]]

③dp数组初始化，本题所给数组中的数都是正整数，所以初始化为0即可

④遍历顺序，滚动数组，先物品后背包，背包倒序

⑤推导dp数组

代码

class Solution {
public:bool canPartition(vector<int>& nums) {// 计算数组中所有元素之和int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 如果和为奇数，则不可能分隔，因为都是数组中都为正整数if (sum % 2 == 1)return false;// target为背包的容量int target = sum / 2;vector<int> dp(target + 1, 0); // 定义dp数组// 01背包，先物品，后背包，背包倒序遍历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;}
};

总结

①01背包问题，m个物品，有各自的重量和价值，背包容量为n，将物品装入到背包里，使得背包中物品的价值总和最大

②选择背包大小为dp数组，dp[j]的含义是背包容量为j时装入物品的最大价值

③再遍历dp数组时，每次都有两个选择，装与不装。当容量不足时就不装，价值与上一状态一样；当容量足够时，装入当前物品有一个价值，上一状态也有一个价值，取最大值

④416.分割等和子集竟然能用01背包解决，属实是意想不到

⑤刚开始接触背包问题，很多细节没有掌握，需要复习