416. 分割等和子集

Alex_Shen
2022-03-29 / 0 评论 / 0 点赞 / 133 阅读 / 554 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。

思路:

分解为0-1背包问题

  • 背包的体积为sum / 2
  • 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
  • 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

最终背包:

image-20220120234146297

代码:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum%2==1)    return false;
        int target=sum/2;
        vector<int> dp(target+1,0);
        for(int i=0;i<nums.size();i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target)  return true;
        return false;
    }
};
0

评论区