dp专题7 分割等和子集

2024-01-02 16:49:33

本题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目:

思路:

由题意,题目意思是给出? 数组 nums? 找出两个子集它们的元素和相等。

这里两个自己的元素和相等,说明需要 数组 nums 总和可以平分,即 sum % 2 == 0

又因为子集不要求我们所取的元素是连续的,这里只有取或不取,所以我们试着取联想以下 01 背包

其中 容量是 我们的 sum / 2 ,只要我们取的 nums 元素之和 刚好满足 sum / 2 即可,所以我们的 元素中的? 价值 和?体积 都是 nums[] 元素值

代码详解如下:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int>dp(200*100+10,0);   // 定义 dp 数组
        int sum = 0;    // 计算 (背包容量) 元素和
        for(int &i:nums) sum += i;
        if(sum % 2) return false;   // 如果元素和无法平分,返回 false
        else sum /= 2;
        
        // 开始遍历元素
        for(int &i:nums)
        {
            // 遍历(背包容量) 到达的平分元素和
            for(int j = sum ;j >= i;--j)
            {
                dp[j] = max(dp[j],dp[j - i] + i);
            }
        }
        
        return dp[sum] == sum;
    }
};

最后提交:

文章来源:https://blog.csdn.net/hacker_51/article/details/135342603
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。