秦皇岛 免费建网站,在线制作图片拼接,舞蹈培训网站模板,widows安装wordpress力扣日记#xff1a;【动态规划篇】416. 分割等和子集 日期#xff1a;2024.4.18 参考#xff1a;代码随想录、力扣 416. 分割等和子集
题目描述 难度#xff1a;中等 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使…力扣日记【动态规划篇】416. 分割等和子集 日期2024.4.18 参考代码随想录、力扣 416. 分割等和子集
题目描述 难度中等 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 提示
1 nums.length 2001 nums[i] 100
题解
class Solution {
public:
#define SOLUTION 2// 思路转换的关键一步将数组分割成两个子集使得两个子集的元素和相等 相当于寻找一个子集其元素和为总和的一半// 这样就从分割找两个子集转换成找一个子集了可以用回溯法解决
#if SOLUTION 1 /*回溯法超出时间限制*/bool canPartition(vectorint nums) {}bool backtracking(vectorint nums) {}
#elif SOLUTION 2 /*动态规划*//*如何转换为 01背包问题并使用动态规划解决原问题需要从nums的所有元素中挑选一些元素放到子集中使得子集中的元素的和为sum/2类比背包问题nums中的元素相当于物品而元素值即为物品的重量子集用来放元素相当于背包从nums中挑元素放入子集相当于挑选物品放入背包即为背包问题由于元素不能重复选即物品只能取1次所以是01背包问题且在这个问题中元素的值物品的重量也等于其价值即weights values子集中的元素总和即为背包的容量即能装的物品的重量总和也即总价值当子集达到元素总和sum/2相当于背包容量装满此时总价值最大所以weights nums(排序后)values nums(排序后)bagsize sum/2*/bool canPartition(vectorint nums) {// 先对nums进行排序sort(nums.begin(), nums.end());// 求bagsize即总和/2int sum 0;for (int i 0; i nums.size(); i) {sum nums[i];}if (sum % 2 ! 0) return false; // 如果和非偶数肯定不能使两子集的和相等int bagSize sum/2;// 动规五部曲// 1. dp数组定义dp[j] 表示 背包容量为j时能得到的最大价值也即能装的最大重量vectorint dp(bagSize 1, 0);// 2. 初始化需要初始化为0已经包含在定义中了// 3. 遍历顺序先物品再背包背包从大到小for (int i 0; i nums.size(); i) {for (int j bagSize; j nums[i]; j--) {// dp[j] max(dp[j], dp[j-weights[i]] values[i])dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}// 如果最后dp[bagSize] bagSize说明容量为bagSize装入的元素的价值即重量为bagSize即刚好能装满if (dp[bagSize] bagSize) return true;return false;}
#endif
};复杂度
时间复杂度 空间复杂度
思路总结
关键在于如何转换为 01背包问题并使用动态规划解决首先要将原题意转换思路将数组分割成两个子集使得两个子集的元素和相等 相当于寻找一个子集其元素和为总和的一半转换后的原问题需要从nums的所有元素中挑选一些元素放到子集中使得子集中的元素的和为sum/2类比背包问题有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 nums中的元素相当于物品而元素值即为物品的重量子集用来放元素相当于背包从nums中挑元素放入子集相当于挑选物品放入背包即为背包问题由于元素不能重复选即物品只能取1次所以是01背包问题且在这个问题中元素的值物品的重量也等于其价值即weights values nums子集中的元素总和即为背包的容量即能装的物品的重量总和也即总价值当子集达到元素总和sum/2相当于背包容量装满此时总价值最大
