代码随想录Day42 | 背包问题理论 416. 分割等和子集
- 二维dp解决背包问题
- 一维dp求解背包问题
- 46.携带研究材料
- 二维dp
- 一维dp
- 416.分割等和子集
二维dp解决背包问题
文档讲解：代码随想录
视频讲解： 带你学透0-1背包问题
状态
利用五部曲来分析二维dp是如何解决背包问题的。
- dp[i][j]的含义
i表示当前第i个物品，j表示背包的容量，dp[i][j]表示从0~i个物品中选取并放入容量为j的背包的价值最大和 - 递推公式
主要有两种情况：- 放入第i个物品超重，即当前的容量小于i的重量，那么dp[i][j] = dp[i-1][j]
- 放入第i个物品不超重，dp[i][] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
- 初始化
- 考虑dp[i][0]：表示容量为0的背包的最大价值为0
- 考虑dp[0][j]: 表示容量为0~j的背包，放入0号物品应该有的价值
- 其余位置初始化为0
- 遍历顺序
先背包再物品，或者先物品再背包都可以。
主要是都要从左上角向dp[i][j]计算 - 打印dp数组
一维dp求解背包问题
本质是对递推公式的考虑进行修改，对于原始的二维dp，dp[i-1][j]来表示上一层的最大价值，上一层可以重复利用，那么直接拷贝到当前层就可以，这样就会少一阶数组。
对于1维的dp，五部曲分析
- dp[j]
j表示背包容量，dp[j]就表示背包在当前容量下的最大价值 - 递推公式
j容量的背包还是考虑是否可以继续装下重量为weight[i]的物品
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]) - 初始化
对于dp[0]，那就是容量为0的背包价值就是0，
对于dp[j]，如果物品价值都是正整数，那么应当初始化为0 - 遍历顺序
双层遍历，先物品再背包，背包必须倒序遍历。主要是为了避免重复计算物品数量。
本质都是右下角的值是通过左上角得到的。但对于一维dp，相当于是右边的值需要左边值来更新。 - 打印dp数组
46.携带研究材料
二维dp
#include <iostream>
#include <vector>int main()
{int M,N;std::cin >> M >> N;//输入材料所占空间std::vector<int> weight(M,0);for(int i = 0;i<M;i++){std::cin >> weight[i];}//输入材料价值std::vector<int> value(M,0);for(int i = 0;i<M;i++){std::cin >> value[i];}//创建二维dpstd::vector<std::vector<int>> dp(M+1,std::vector<int>(N+1,0));//初始化dpfor(int j = 0;j<N+1;j++){if(j<weight[0]){dp[0][j] = 0;}else{dp[0][j] = value[0];}}//遍历for(int i =1;i<M+1;i++){for(int j = 0;j<N+1;j++){if(j<weight[i]){dp[i][j] = dp[i-1][j];}else{dp[i][j] = std::max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}}std::cout << dp[M][N];
}
一维dp
#include <iostream>
#include <vector>int main()
{int M,N;std::cin >> M >> N;//输入材料所占空间std::vector<int> weight(M,0);for(int i = 0;i<M;i++){std::cin >> weight[i];}//输入材料价值std::vector<int> value(M,0);for(int i = 0;i<M;i++){std::cin >> value[i];}//创建一维dpstd::vector<int> dp(N+1,0);//初始化 全部为0//遍历for(int i = 0;i<M+1;i++){for(int j = N;j>=weight[i];j--){dp[j] = std::max(dp[j],dp[j-weight[i]]+value[i]);}}std::cout<<dp[N];
}
416.分割等和子集
文档讲解：代码随想录
视频讲解： 动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集
状态
如何转换为背包问题
- 本题求解就是在数组中搜索元素（物品）然后它们的和为sum/2（价值）
- 重量如何确定–重量就是价值，当重量和价值相等时表示能够搜索到。即背包正好装满
五部曲
- dp[j]
j表示当前重量，dp[j]表示当前重量下的价值和。
j容量的背包还是考虑是否可以继续装下重量为weight[i]的物品 - 递推关系
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]) - 初始化
对于dp[0]，那就是容量为0的背包价值就是0 - 遍历顺序
先物品再背包，背包倒序 - 打印dp
//求和为sum/2的元素和
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;int target = sum/2;//dp数组vector<int> dp(target+1,0);//初始化都为0， 全为正整数for(int i = 0;i<nums.size();i++){for(int j = target;j>=nums[i];j--){//nums[i]为重量 也为价值dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[target] == target) return true;return false;}
};
