力扣日记：【动态规划篇】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，相当于背包容量装满，此时总价值最大
