代码随想录算法训练营 Day30 | 动态规划 part03

46. 携带研究材料第六期模拟笔试题目描述小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。输入描述第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。第二行包含 M 个正整数代表每种研究材料的所占空间。第三行包含 M 个正整数代表每种研究材料的价值。输出描述输出一个整数代表小明能够携带的研究材料的最大价值。输入示例6 12 2 3 1 5 22 3 1 5 4 3输出示例5// 二维数组解法 #include iostream #include vector using namespace std; int main(){ int m, n; // m: 物品数量, n: 背包容量 cin m n; // dp[i][j] 表示从前 i 个物品中选择放入容量为 j 的背包能获得的最大价值 vectorvectorint dp(m 1, vectorint(n 1, 0)); vectorint weight(m 1); vectorint value(m 1); // 读入数据下标从 1 开始方便对应第几个物品 for(int i 1; i m; i) cin weight[i]; for(int i 1; i m; i) cin value[i]; // 初始化虽然 vector 默认为 0但在逻辑上 // dp[0][j] 0 (没有物品可选价值为 0) // dp[i][0] 0 (背包容量为 0装不下价值为 0) // 遍历物品 for(int i 1; i m; i){ // 遍历背包容量正序遍历 for(int j 0; j n; j){ if(j weight[i]) { // 当前背包容量装不下第 i 个物品只能继承前 i-1 个物品的结果 dp[i][j] dp[i - 1][j]; } else { // 可以装下第 i 个物品面临两个选择 // 1. 不装价值 dp[i-1][j] // 2. 装价值 dp[i-1][j-weight[i]] value[i] (留出第 i 个物品的空间) // 取两者最大值 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); } } } // 输出结果前 m 个物品放入容量 n 的背包的最大价值 cout dp[m][n]; return 0; } // 一维数组解法 #include iostream #include vector using namespace std; int main(){ int m, n; cin m n; // dp[j] 表示容量为 j 的背包能装下的最大价值 // 滚动数组思想每次计算第 i 层时直接覆盖在第 i-1 层的数组上 vectorint dp(n 1, 0); vectorint weight(m 1); vectorint value(m 1); for(int i 1; i m; i) cin weight[i]; for(int i 1; i m; i) cin value[i]; // 遍历物品 for(int i 1; i m; i){ // 遍历背包容量必须逆序遍历从大到小 // 为什么逆序 // 保证计算 dp[j] 时dp[j - weight[i]] 保存的是上一轮即不包含当前物品 i的数据。 // 如果正序遍历dp[j-weight[i]] 已经被更新为包含物品 i 的数据会导致物品 i 被重复添加。 for(int j n; j weight[i]; j--){ dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } cout dp[n]; return 0; }总结1. 核心区别遍历顺序特性二维解法dp[i][j]一维解法dp[j]遍历顺序正序遍历背包容量j逆序遍历背包容量j原因dp[i][j]依赖的是上一层dp[i-1][...]。因为i-1层的数据在二维数组中是独立保存的无论j怎么变都不会覆盖上一层的数据所以正序没问题。dp[j]依赖的是“旧值”。如果正序遍历计算dp[j]时dp[j-weight[i]]已经被更新成“当前物品也考虑进去”的新值了这会导致同一个物品被重复使用变成完全背包。逆序保证了我们用的是上一轮的“旧数据”确保每个物品只取一次。2. 状态转移方程对比二维dp[i][j] max(dp[i-1][j], dp[i-1][j - w] v)物理意义清晰明确区分“上一行”和“当前行”。一维dp[j] max(dp[j], dp[j - w] v)简洁优雅等号右边的dp[j]其实就是隐式的dp[i-1][j]。3. 初始化细节二维需要初始化第一行和第一列通常是 0。一维全部初始化为 0。因为dp[j]代表最大价值没装东西时价值自然为 0。416. 分割等和子集给你一个 只包含正整数 的 非空 数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。class Solution { public: bool canPartition(vectorint nums) { // 1. 计算总和 int sum 0; for(int i : nums) sum i; // 2. 特判如果总和是奇数必然无法分割成两个相等的子集 if(sum % 2 1) return false; // 3. 转化为背包问题 // 目标寻找是否存在子集使其和为 sum/2 // 背包容量target sum/2 // 物品重量nums[i] // 物品价值nums[i] (重量 价值) int n sum / 2; vectorint dp(n 1, 0); // 4. 0-1 背包求解过程 for(int i 0; i nums.size(); i){ // 遍历背包容量必须逆序保证每个数字只用一次 for(int j n; j nums[i]; j--){ // 递推公式 // dp[j] 表示容量为 j 的背包能装下的最大数值总和 // 因为数值本身既是重量也是价值所以这里 nums[i] dp[j] max(dp[j], dp[j - nums[i]] nums[i]); } } // 5. 判断结果 // 如果 dp[n] (容量为 n 的背包能装的最大价值) 等于 n // 说明正好装满了找到了和为 sum/2 的子集 return dp[n] n; } };总结1. 为什么是 0-1 背包物品数组中的每个数字。重量数字的值nums[i]。价值数字的值nums[i]。背包容量目标和sum / 2。选择每个数字只能用一次选或不选这正是 0-1 背包 的典型特征。2. 为什么dp[j] max(..., dp[j-nums[i]] nums[i])在标准的背包问题中我们要的是max(不选, 选)来获取最大价值。在这里因为 价值 重量我们其实是在求 “背包能装下的最大重量”。如果dp[target] target意味着背包被 正好装满 了也就找到了一个子集的和等于target。3. 复杂度分析时间复杂度O(N×M)其中 N 是数组长度M 是sum/2。空间复杂度O(M)。