赞
踩
给你一个 只包含正整数的 非空数组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
先假设sum
为数组的总和,需要确定是否可以将这个数组分割成两个元素和相等的子集,只要集合中出现总和sum/2
的子集,就可以算这个数组可以分割成两个元素和相等的子集。也就是从数组从选出部分元素,使元素总和恰好为sum/2
,推导到这里就可以用动态规划的经典理论0-1背包来解决问题。
dp[i]=max(dp[i],dp[j-nums[i]]+nums[i])
100
,数组的长度不会超过200
,那么总和不会大于20000
,背包的最大容量只需要其中一半,所以10001
就足够了。for
循环放在内层,且内层for
循环使用倒叙遍历。// 编程软件:VS2019 // 参考书籍:代码随想录 #include<iostream> #include<vector> #include<algorithm> using namespace std; // 时间复杂度O(n的平方),空间复杂度O(n) bool canPartition(vector<int>& nums) { int sum = 0; vector<int> dp(10001, 0); // 计算数组总和 for (int i = 0; i < nums.size(); i++) { sum += nums[i]; } // 如果数组总和为奇数,那么是不可能分成两个元素和相等的子集,直接返回false if (sum % 2 == 1) return false; int target = sum / 2; // 0-1背包逻辑 for (int i = 0; i < nums.size(); i++) { // 每一个元素一定不能重复放入背包,所以for循环是从大到小遍历的 for (int j = target; j >= nums[i]; j--) { dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); } } // 判断是否恰好为target if (dp[target] == target) return true; return false; } int main() { vector<int>nums = { 1,5,11,5 }; if (canPartition(nums)) cout << "true"; else cout << "false"; } // 结果:true
要学会从题目的要求出发,逆向的推导问题,将问题本质与学过知识联系。就像本题,从是否可将数组分割成两个元素和相等的子集出发,推导出从数组选取部分元素,而这些元素之和若恰好为
sum/2
,则说明符合题目要求,这就与
0-1背包碰上了。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。