当前位置：首页 > news >正文

代码随想录打卡Day35

news 2024/9/25 5:32:40

今天还是以看视频为主，主要是力扣上合适的题目不多，今天主要是学习0-1背包的二维数组解法和一维数组解法，今天题目不多，但是debug花了我好久时间。。。主要还是对0-1背包不够熟悉。

46. 携带研究材料（卡码网）

这道题我先用二维dp数组来做的，dp[i][j]的含义就是：对于容量为j的背包，通过合理选择物品[0,i]的组合，所能达到的最大价值即为dp[i][j]。
二维数组的初始化需要明确几点：1.dp数组大小 2.初始化哪些地方
第1点，对于m种物品，最大容量为n的背包，我们需要定义一个m行n+1列的二维向量；
第2点，初始化下标为0的行和列，对于j = 0，背包容量为0，自然装不下任何东西，所装物品的价值也为0，对于第一个（下标为0）物品（不一定是负重最小），当背包容量依次为1，2，…，n时，背包的价值只有两种取值，要么是0（背包装不下），要么是value[0]（背包装得下，value[0]是物品0的价值）。
接下来就是确定递推公式，对于dp[i][j]，
当背包选择不装物品i或是空背包都无法装下物品i时，dp[i][j] = dp[i - 1][j];
当背包选择装下物品i时，dp[i][j] = dp[i - 1][j - weight[i]] + value[i];
装下了物品i不一定能带来更高的价值，有可能物品i的负重很大，但是价值却很小，所以我们需要在两种情况下取最大值。
在二维dp数组中，先遍历背包容量还是先遍历物品都是可以的。

#include<iostream>
#include<vector>
#include <algorithm>using namespace std;int main(){//数据读取int M, N;vector<int> value;vector<int> weight;cin >> M;cin >> N;int input;for(int i = 0; i < M; i++){cin >> input;weight.push_back(input);}for(int i = 0; i < M; i++){cin >> input;value.push_back(input);}//开始动态规划vector<vector<int>> dp(M, vector<int>(N + 1)); //初始化为全0数组//dp数组初始化for(int i = 0; i < M; i++)dp[i][0] = 0;for(int i = 1; i <= N; i++){if(i < weight[0])  //背包装不下第一个物品dp[0][i] = 0;elsedp[0][i] = value[0];}int MAX = *max_element(dp[0].begin(), dp[0].end());//开始遍历递推dp数组for(int i = 1; i < M; i++){for(int j = 1; j <= N; 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]);MAX = max(dp[i][j], MAX);}}cout << MAX << endl;return 0;
}

如果将二维数组降维成一维数组，则dp[j]的含义为背包容量为j时的最大价值，则初始化就非常简单了，假设背包最大容量为N定义一个大小为N+1的一维全零向量即可。在递推过程中，dp[j] = max(dp[j], dp[j - weight[i]] + value[i]),当然，j < weight[i]的情况下，无需对dp[j]进行改动。在遍历顺序上，必须先遍历物品再遍历背包，因为一维数组会反复利用，在每一层外循环结束后，dp数组中保存的值都是考虑加入物品i后的最优选择下的最大价值，在遍历背包时必须倒序遍历，确保同一种物品只被添加一次。

416. 分割等和子集

这道题目我把部分思路都想出来了，想到了判断数组求和除以二，想到了用一维dp数组来做，但是还是没有想明白，最后只能看视频，这道题目的巧妙之处在于使背包的最大容量为sum / 2，物品就是数组里面的数字，数组里的数字既代表了物品的负重，也代表了物品的价值，所以本题遍历时的原则就是在背包装得下的情况下，负重越大越好。在循环过程中，一旦发现在背包负重为sum / 2时，价值也达到了sum / 2，就说明数组能够分割成两个总和相等的子数组。当然，在对输入数组求和后，需要先判断sum的奇偶性，如果为奇数的话直接返回false即可（无论如何也分不出来），为偶数的话再进行动态规划五部曲。

class Solution {
public:bool canPartition(vector<int>& nums) {//1.确定dp[j]的含义：[0, j]的数字中最优组合的最大价值//2.确定递推公式  dp[j] = max(dp[j], dp[j - weight[i]] + value[i])//3.dp数组初始化 dp初始化为0向量//4.确定遍历顺序：先物品(数字)，再背包(从后往前)//5.打印数组(省略)int sum = accumulate(nums.begin(), nums.end(), 0);//若总和为奇数则无法平分if(sum % 2 != 0) return false;//以下代码为总和为偶数情况vector<int> dp(sum / 2 + 1, 0);  for(int i = 0; i < nums.size(); i++){for(int j = dp.size() - 1; j >= 1; j--){if(j < nums[i]) break;  //装不下dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);if(dp[j] == sum / 2) return true;}}return false;}
};