每日一题——分割等和子集

偷还是不偷 416. 分割等和子集 给你一个 只包含正整数 的 非空 数组 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 背包，能平分，说明肯定整除2,否则直接false 最后数字累加，累加和平分一半，看一半的容量能不能放满，如果能满，可说明可以分割，否则就是不行。 dp[j] 代表背包容量所能累加（能偷）的最大值 最外层循环代表能偷的物品个数

除了一行，每个空格代表对应重量可偷物品的最大价值

物品 [1,5,11,5]

如果重量从小到大，会演变成多重背包，一个物品会重复放多次

for (int j =0; j>=nums[i]&&j<=weight; j++) {
          
   

      dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);

}

题目算法代码如下

public class 分割等和子集 {
          
   
    public boolean canPartition(int[] nums) {
          
   
        if (nums.length==0||nums==null){
          
   
            return false;
        }
        int sum=0;
        for (int num : nums) {
          
   
            sum+=num;
        }
        if (sum%2!=0){
          
   
            return false;
        }
        int weight =sum/2;
        int dp[]=new int[weight+1];
        //里面的物品
        for (int i = 0; i < nums.length; i++) {
          
   
            for (int j =weight; j>=nums[i]; j--) {
          
   
                //不偷dp[j]   偷dp[j-nums[i]]+nums[i]
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[weight]==weight;
    }
}