[数据结构与算法]【Leetcode】背包问题-416. 分割等和子集

【Leetcode】背包问题-416. 分割等和子集

题目

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

思路

• 如果可以分割等和子集 那么背包中正好装下一半的数值 sum / 2
• 背包要放进的物品是元素的数值，价值也是元素的数值
• 每一个元素只能放入一次
• 确定dp数组 的含义
• dp[j]表示容量为j的背包最大容量的物品价值
• 确定一维dp数组推导公式
• dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
• 题目给出的元素都是正整数 所以dp数组全部初始化为0 如果有负数 全部初始化为负无穷
• 保证dp数组在递归公式中取得是最大值 而不是被初始值覆盖

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 如果可以分割等和子集 那么背包中正好装下一半的数值 sum / 2
        // 背包要放进的物品是元素的数值，价值也是元素的数值
        // 每一个元素只能放入一次

        // 计算目标数值 target  = sum / 2
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
        }

        if(sum % 2 == 1)
        {
            return false;
        }

        int target = sum / 2;

        // 确定dp数组 的含义
        // dp[j]表示容量为j的背包最大容量的物品价值
        vector<int> dp(10001,0);

        // 确定一维dp数组推导公式
        // dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
        // 题目给出的元素都是正整数  所以dp数组全部初始化为0  如果有负数 全部初始化为负无穷
        // 保证dp数组在递归公式中取得是最大值  而不是被初始值覆盖

        // 先遍历Nums数组  在遍历背包 这里的bagWeight = sum / 2
        // 记住模板
        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;
        
    }
};