-爱代码爱编程
_36LeetCode代码随想录算法训练营第三十六天-动态规划背包问题
题目列表
- 01背包问题,你该了解这些!
- 01背包问题,你该了解这些!滚动数组
- 416.分割等和子集
代码随想录地址
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://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://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
01背包问题,你该了解这些!
背包问题分类
背包问题的经典资料当然是:背包九讲,已经下载,是竞赛级别的,学有余力计划去看看。
标准背包问题
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
举例:
背包最大重量为4。
物品为:
重量 | 价值 | |
---|---|---|
物品0 | 1 | 15 |
物品1 | 3 | 20 |
物品2 | 4 | 30 |
问背包能背的物品最大价值是多少?
背包问题暴力解法
每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是 o ( 2 n ) o(2^n) o(2n),这里的n表示物品数量。(这种方式在力扣上面会超时)
动态规划解决背包问题
思路
- 确定dp数组以及下标的含义
dp[i] [j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
- 确定递推公式
此递推公式的前提为:重量越大,价值越高。
不放物品i:背包容量为j,当物品i的重量大于背包j的重量时,物品i无法放进背包中,此时dp[i] [j]就是dp[i - 1] [j]。
放物品i:背包容量为j,当物品i的重量小于等于背包j的重量时,物品i可以放进背包中;当物品i的重量等于背包的容量时,直接将物品i放进背包即可获得最大价值;当物品i的重量小于背包的容量时,为了将背包尽量塞满,就要找到背包的容量为j - weight[i]时的最大价值,然后加上value[i]即可获得价值最大值。
递归公式: dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);
- 初始化dp
1.当背包容量为0时,背包价值总和一定为0;此时需要初始化背包为0时的所有dp。
2.状态转移方程 dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。
当 j < weight[0]的时候,dp[0] [j] 应该是 0。
当j >= weight[0]时,dp[0] [j] 应该是value[0],因为背包容量放足够放编号0物品。
3.其他的dp元素可以根据递推公式求得。
- 遍历顺序
两个遍历的维度:物品与背包重量。
本题中先遍历物品和先遍历背包重量都可以,主要根据递推公式来判断。
代码
void test_2_wei_bag_problem1() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagweight = 4;
// 二维数组 全部初始化为0
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++) { // 遍历物品
//此处为什么不从j = weight[i]开始,因为需要将j<weight[i]的dp[i][j]复制过去
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();
}
02背包问题,你该了解这些!滚动数组
思路
对于二维背包问题,其实完全可以用一维数组解决问题。
使用二维数组的时候,递推公式: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[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组)。
动态规划五部曲
- 确定dp数组的定义
在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。
- 一维dp数组的递推公式
根据二维背包问题的递推公式,将前一层变为当前层即可。
所以递推公式为:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 一维dp数组如何初始化
将所有元素初始化为0。根据递推公式可知,每次更新dp元素,都会将其与自己相比并且取较小值,因此初始化dp数组时应该将其赋值为正数的最小值,以减少干扰。
- 一维dp数组遍历顺序
两层for循环,一层背包,一层物品,如何确定先遍历背包还是先遍历物品?
如何确定从大到小遍历还是从小到大遍历?
如果一层循环遍历物品,二层循环遍历背包,是可以的,但是在遍历背包时需要倒叙遍历,是为了防止一个物品加入多次。
如果一层循环遍历背包,二层循环遍历物品:对于滚动数组,每个容量下的背包都只会装一个物品,原因是对于背包一定是倒序遍历的。这种遍历方式是不正确的。
- 举例推导dp数组
这个就自己心算了。
代码
#include<iostream>
#include<vector>
using namespace std;
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++) { // 遍历物品
//这里为什么可以到j >= weight[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.分割等和子集
题目
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
思路
分析
- 背包的体积为sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
动规五部曲:
- 确定dp数组以及下标的含义
01背包中,dp[j] 表示: 容量为j的背包,所背的物品价值最大可以为dp[j]。
- 确定递推公式
递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- dp数组如何初始化
首先dp[0]一定是0,因为容量为0的背包所背物品价值最大可以为0。
如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,如果题目给的价值有负数,那么非0下标就要初始化为负无穷。
这样才能让dp数组在递推的过程中取得最大的价值,而不是被初始值覆盖了。
- 确定遍历顺序
在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中就已经说明:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
- 举例推导dp数组
如果dp[j] == j 说明,集合中的子集总和正好可以凑成总和j,理解这一点很重要。
代码
- 时间复杂度:O(n^2)
- 空间复杂度:O(n),虽然dp数组大小为一个常数,但是大常数
/*
* @lc app=leetcode.cn id=416 lang=cpp
*
* [416] 分割等和子集
*/
// @lc code=start
class Solution {
public:
bool canPartition(vector<int>& nums) {
//因为是分为两组,因此求得target表示其中一组元素的总和
int sum = 0;
for(int data : nums)
sum += data;
//如果sum/2会得小数,那么肯定不可能分为两组
if(sum % 2 == 1)
return false;
int target = sum / 2;
//dp数组定义及其初始化
vector<int> dp(target + 1, 0);
//遍历物品和背包
for(int i = 0; i < nums.size(); i++)//遍历物品,其实就是nums中的元素
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;
else
return false;
}
};
// @lc code=end