力扣日记4.18-【动态规划篇】416. 分割等和子集

本文主要是介绍力扣日记4.18-【动态规划篇】416. 分割等和子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣日记：【动态规划篇】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 <= 200
1 <= nums[i] <= 100

题解

class Solution {
public:
#define SOLUTION 2// 思路转换的关键一步：将数组分割成两个子集，使得两个子集的元素和相等 => 相当于寻找一个子集，其元素和为总和的一半！// 这样就从分割找两个子集转换成找一个子集了，可以用回溯法解决
#if SOLUTION == 1  /*回溯法（超出时间限制）*/bool canPartition(vector<int>& nums) {}bool backtracking(vector<int>& 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(vector<int>& nums) {// 先对nums进行排序sort(nums.begin(), nums.end());// 求bagsize（即总和/2）int 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时能得到的最大价值（也即能装的最大重量））vector<int> 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，相当于背包容量装满，此时总价值最大