本文主要是介绍【0-1背包】力扣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:bool canPartition(vector<int>& nums) {int n = nums.size();if(n < 2){return false;}int sum = 0;int maxNum = 0;for(int i = 0; i < n; i++){sum += nums[i];maxNum = max(maxNum, nums[i]);}if(sum & 1){return false;}int target = sum / 2;if(maxNum > target){return false;}vector<int> dp(target + 1, 0);dp[0] = true;for(int i = 0; i < n; i++){for(int j = target;j >= nums[i]; j--){dp[j] |= dp[j-nums[i]];}}return dp[target];}
};
首先先判断数组可以被分割成等和子集的必要特征,当数组大小小于2的时候,返回false。接着计算出总和sum和最大的元素maxNum,当sum是奇数的时候,返回false,当最大元素大于sum / 2的时候,也返回false。
dp[j] |= dp[j-nums[i]];
使用或运算,dp[j] 中的 j 代表的是当前要检查的子集和,也就是在给定的数组中,是否可以找到一个子集,使得这个子集的元素和等于 j。
在遍历数组 nums 时,对于每个元素 nums[i],我们从 target 开始逆序遍历到 nums[i],并更新 dp[j]:
例如,当我们处理 nums[i] = 5 时:
我们会检查 dp[11] 是否可以由 dp[11-5] 转化而来,即 dp[6] 如果为 true,那么 dp[11] 也可以变为 true。类似地,dp[6] 可以由 dp[6-5] = dp[1] 转化而来。通过这种方式,dp[j] 会被不断更新,最终 dp[target] 如果为 true,说明存在一个子集和等于 target。
这篇关于【0-1背包】力扣416. 分割等和子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!