[LeetCode]Dp416 分割等和子集 [01背包]

🚩传送门：https://leetcode-cn.com/problems/partition-equal-subset-sum/

题目

给你 只包含正整数 的 非空 数组 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

解题思路：动态规划 [ 01背包模型 ]

整个问题换个问法，能否用容量为总体积一半的背包装下总体积一半的物品

🚩01背包传送门：https://www.yuque.com/qingxuan-u4juc/leetcode/up7w1w

( 重点可以查看一下倒序遍历的原因 )

👉 定义 为容量为 的背包最多能装下的物品的总体积大小 。

我们需要考虑的其实就是，🟢当前物品能不能放进去 ？ 若能放进去，我们🔵考虑放不放进去 ？

🟢容量总背包大于当前物品的体积就可以放进去 。
🔵当前物品放进去后的背包所能装的总体积大于不放进去所能装的总体积就放进去，否则不放 。
🔴1. dp[j]代表当前容量 j 背包最多能装下的物品的总体积大小 。
2. dp[j-nums[i]] 代表装当前物品后，背包剩余容量 。
3. nums[i] 代表当前物品 i 的体积 。

状态转移方程：

复杂度分析

时间复杂度：，其中 为数组 的长度， 为物品总体积的一半。

空间复杂度：，只需要创建总体积一半的容量背包即可。

代码

我的代码

public class Demo {
    //将题目换成:能否用容量为总体积一半的背包装下总体积一半的物品?
    //dp[capacity]代表了当前容量背包所能装的最大容量物品
    public static boolean canPartition(int[] nums) {
        //1. 求nums总和,即总的物品体积
        int capacity= Arrays.stream(nums).sum();
        //2. 奇数体积不可平分
        if(capacity%2==1)return false;
        //3. 定义容量背包,容量为总体积的一半
        int[]dp=new int[(capacity/2)+1];
        //4. 从第一个物品开始遍历,容量逐渐减少,判断是否需要存放
        for (int i = 0; i < nums.length; i++) {
            for (int j =(capacity/2); j >=  nums[i];j--) {//此条件确保了物品定能存放进去
                //5. 是否需要存放考虑,放进去的收益和不放进去的收益
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        //如果容量为总体积一半的背包最大能装下总体积一半的物品,说明可以分割
        if(dp[capacity/2]==capacity/2)return true;
        return false;
    }
    public static void main(String[] args) {
        int[]nums={1,5,11,5};
        System.out.println(canPartition(nums));
    }
}