1背包问题,你该了解这些!
链接:代码随想录
视频链接:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili
完全背包:有n种物品,每种物品有无限个。
0-1背包:有n种物品,每种物品有1个。
应用类题目比较多,没有纯粹的0-1背包。
暴力解法:回溯,时间复杂度2的n次方
一、二维数组讲解0-1背包
给个例子,自己手推一下。
例子:
对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
void test_2_wei_bag_problem1() { 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]; } // 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]); } } cout << dp[weight.size() - 1][bagweight] << endl; } int main() { test_2_wei_bag_problem1(); }
二、一维滚动数组讲解0-1背包
(建议死记硬背,并不好理解)
1、dp[j]的代表
dp[j]为 容量为j的背包所背的最大价值
2、
dp[j]可以通过dp[j - weight[i]]推导出来,dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。
此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值,
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3、一维dp数组如何初始化
dp[0]=0
注:背包要倒序遍历,且先遍历物品,再遍历背包
void test_1_wei_bag_problem() { 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--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[bagWeight] << endl; } int main() { test_1_wei_bag_problem(); }
416. 分割等和子集
链接:代码随想录
分析:和0-1背包放在一起。。。分成两个子集,子集元素和相等
先算出来sum.两个子集,子集元素和相等,则子集只需要装到sum/2
dp[i]代表从[0,i]中选出来一些数相加的和
如果包含最后一个数nums[i], dp[i-1]+nums[i]
不包含最后一个数nums[i],dp[i-1]
然后如果dp[i]==(dp[i-1]+nums[i])==sum/2
==dp[i-1]
写不出来代码。。。看答案。答案用到了一维dp数组。
不好理解,建议一定要看代码随想录!!!最后理解的程度大概60%?自己能写出来。
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; // dp[i]中的i表示背包内总和 // 题目中说:每个数组中的元素不会超过 100,数组的大小不会超过 200 // 总和不会大于20000,背包最大只需要其中一半,所以10001大小就可以了 vector<int> dp(10001, 0); for (int i = 0; i < nums.size(); i++) { sum += nums[i]; } // 也可以使用库函数一步求和 // int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2 == 1) return false; int target = sum / 2; // 开始 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]); } } // 集合中的元素正好可以凑成总和target if (dp[target] == target) return true; return false; } };