【代码随想录算法训练营第34天】动态规划part03 | 01背包问题 二维 | 01背包问题 一维 | 416. 分割等和子集

KEY

（1）语法

1> 如何初始化二维数组

intm=3,n=4;// 创建一个 3 行 4 列的二维 vector，全部元素初始化为 0vector<vector<int>>dp(m,vector<int>(n,0));// 如果想全部初始化为 -1 或其他值：vector<vector<int>>dp(m,vector<int>(n,-1));

2> 数组求和用accumulate(v.begin(), v.end(), 0);

accumulate(v.begin(),v.end(),0);

（2）学会把问题理解成01背包问题的形式，然后用01背包的套路去解决

01背包问题 二维

• 别看卡尔的视频，看算法课本上的说法即可（两个都对，但是数组大小定义不太一样，别搞混了）
• 这是课本，注意红框两个部分即可
  
  

整个代码：

#include<bits/stdc++.h>using namespace std;intmain(){intm,n;cin>>m>>n;vector<int>w(m);vector<int>v(m);for(inti=0;i<m;i++){cin>>w[i];}for(inti=0;i<m;i++){cin>>v[i];}vector<vector<int>>dp(m+1,vector<int>(n+1,0));for(inti=0;i<m+1;i++){dp[i][0]=0;}for(inti=0;i<n+1;i++){if(i<w[0]){dp[0][i]=0;}else{dp[0][i]=0;}}for(inti=1;i<m+1;i++){for(intj=1;j<n+1;j++){if(w[i-1]>j)dp[i][j]=dp[i-1][j];else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);}}}cout<<dp[m][n];}

01背包问题 一维

核心：

• 把原来的二维数组换成只有一行的一维数组，节省空间
• 注意：这一行是从后往前遍历，因为下图：
  

整个代码：

#include<bits/stdc++.h>using namespace std;intmain(){intm,n;cin>>m>>n;vector<int>w(m);vector<int>v(m);for(inti=0;i<m;i++){cin>>w[i];}for(inti=0;i<m;i++){cin>>v[i];}// vector<vector<int>> dp(m+1,vector<int>(n+1,0));vector<int>dp(n+1,0);for(inti=1;i<m+1;i++){for(intj=n;j>0;j--){if(w[i-1]>j)dp[j]=dp[j];else{dp[j]=max(dp[j],dp[j-w[i-1]]+v[i-1]);}}}cout<<dp[n];}

416. 分割等和子集

关键在于问题建模

思路

题意：把数组划分成两个子集，是左边这样，而不是右边这样

所以，相当于找到这个数组的一个子集，让其和等于数组之和的 1 / 2，这样剩下的其他数之和也为数组之和的 1 / 2

⇒ 相当于一个01背包问题，需要找到合适的物品组合，让其和为数组之和的 1 / 2

• 注意，与01背包相比，背包问题中的weight[],value[]在这里都为nums[]

注： 但是这样做虽然通过了，但是耗时多，carl网用的是一维数组等方法。如果需要提速，可去看，我目前没看。

整个代码：

class Solution{public:boolcanPartition(vector<int>&nums){intsize=nums.size();intc;c=accumulate(nums.begin(),nums.end(),0);if(c%2==1)returnfalse;else{c=c/2;}vector<vector<int>>dp(size+1,vector<int>(c+1,0));for(inti=1;i<size+1;i++){for(intj=1;j<c+1;j++){if(nums[i-1]>j)dp[i][j]=dp[i-1][j];else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1]);}}}if(dp[size][c]==c)returntrue;returnfalse;}};

第九章 动态规划part03

正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。

如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解 这是干什么的。

如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。

背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。

详细布置

01背包问题 二维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
视频讲解：https://www.bilibili.com/video/BV1cg411g7Y6

01背包问题 一维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
视频讲解：https://www.bilibili.com/video/BV1BU4y177kY

416. 分割等和子集
     本题是 01背包的应用类题目
     https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
     视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE