0-1背包问题 力扣416 分割等和子集 java实现

目录

问题描述

要素提取

两个子集的元素和相等。

子集的元素和

难点突破（0-1背包在本题中的应用）

本题思路

状态定义与状态转移方程

代码实现

---

问题描述

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

要素提取 两个子集的元素和相等。

两个子集的元素和相等，那么整个数组元素的和一定是一个偶数。两个相等的偶数相加或者两个相等的奇数相加一定都是一个偶数。

子集的元素和

在一个集合中找到若干个数，使它的和恰好为某个值，每个元素都只能被使用一次。这是一个0-1背包问题。

难点突破（0-1背包在本题中的应用） 本题思路

0-1背包的特点是【每个数只能用一次】。解决的基本思路是【物品一个一个去选，容量也一点点去加】在加的过程中考虑保留或是丢弃这个物品。

本题初始化一个nums.length行，target + 1列的二维数组。len行表示物品的数量，target + 1列表示背包的容量。容量要 +1 是因为背包问题一般需要初始条件，本题的初始条件也就是当背包容量为0时，能装的物品数量也是0【没有物品能够装进去】。

状态定义与状态转移方程

状态定义：dp[i][j] 表示从数组[0,i]中挑选一些数字，使得这些数字的和恰好为 j。

状态转移方程：若物品容量等于当前容量那么一定是true。

选择不装第 i 个物品，如果选择在[0,i-1]这个子区间区间内已经有元素和等于 j 那么为true。

选择装第 i 个物品，在[0,i-1]这个子区间内有元素的和为 j-nums[i] 那么为true

注意事项：确保数组下标不能越界。i-1 要 大于等于 0 ，j-nums[i] 要大于等于0

当容量为 0 时，没有物品能装进去所以第一列全部为 false。

 

代码实现

class Solution {
    boolean ans = false;

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {//如果和为奇数，一定不存在两个相等的子集和
            return false;
        }
        int target = sum/2;

        boolean[][] dp = new boolean[nums.length][target + 1];
        for(int i = 0;i < target + 1;i++) {//容量为0时，没有物品能够放进去
            dp[0][i] = false;
        }
        
        for(int i = 0;i < nums.length;i++) {
            for(int j = 0;j < target + 1;j++) {
                boolean b1 = false;
                boolean b2 = false;
                
                if (i-1 >= 0) {
                    b1 = dp[i-1][j];//在数组范围[0,i-1]中存在元素的和为j吗？
                    if (j - nums[i] >= 0) {
                        b2 = dp[i-1][j - nums[i]];//在数组范围[0,i-1]中存在元素的和为j-nums[j]吗？
                    }
                    
                }
                
                dp[i][j] = b1 || b2 || nums[i] == j;
            }
        }
        return dp[nums.length-1][target];
    }
}