Leetcode skimming: dynamic programming 08 (segmentation and subsets)

416. To divide into equal and subsets

Force button topic link

Difficult topic ： secondary

Given a non empty array containing only positive integers . Whether the array can be divided into two subsets , Make the sum of the elements of the two subsets equal .

Be careful :
No more than elements per array 100
The size of the array will not exceed 200

Example 1:
Input : [1, 5, 11, 5]
Output : true
explain : Arrays can be divided into [1, 5, 5] and [11].

Example 2:
Input : [1, 2, 3, 5]
Output : false
explain : An array cannot be divided into two elements and equal subsets .

Tips ：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

      regard as  01 knapsack problem 
      Array and   Is constant  ,  amount to   Total capacity  weight
             Altogether n  Number 
                      Each number can only be selected once 
                         Once there is a total   and   by  1/2 sum  , That's the end 
     The sum is an odd number and returns directly , Where does odd number come from square 
     Take the number of numbers as the horizontal , All capacity changes are vertical , common  allSun/2+1 Columns 
    dp[i][j] Is the maximum sum of the current position 
     On initialization , The first 0 The column capacity is 0, Initialize to 0                    
     The first line initializes , If the current position can put down this number , Record , Otherwise, initialize to 0
     The first column is initialized to 0, because 0 No one can let go 
     If the first dp[i-1][j] by allsum/2, Then find the target value , return 
     If nums[i]+dp[i-1][j]>result, That is, the current value plus the previous value is larger than the total required , Then use the previous .
     If equal, find , Just go back to 
     If small , Then take the maximum value between the previous value and this value 

package com.programmercarl.dynamic;

/** * @ClassName CanPartition * @Descriotion TODO * @Author nitaotao * @Date 2022/7/27 0:36 * @Version 1.0 * https://leetcode.cn/problems/partition-equal-subset-sum/ * 416.  To divide into equal and subsets  **/
public class CanPartition {
    
    public boolean canPartition(int[] nums) {
    
        /**  regard as  01 knapsack problem   Array and   Is constant  ,  amount to   Total capacity  weight  Altogether n  Number   Each number can only be selected once   Once there is a total   and   by  1/2 sum , That's the end  */
        int allSum = 0;
        for (int i = 0; i < nums.length; i++) {
    
            allSum += nums[i];
        }
        int n = nums.length;
        if (allSum % 2 == 1 || n == 1) {
    
            //  How can odd numbers be divided equally , Where does a number come from 
            return false;
        }
        // x Shaft length 
        int result = allSum / 2;
        //dp[i] Is the current occupied capacity 
        int[][] dp = new int[n][result + 1];
        // altogether n Number , The sum of common needs （ Space ） by  [0,result]
        for (int i = 0; i < n; i++) {
    
            // The first column is initialized to 0, namely sum Still bad 0 when 
            dp[i][0] = 0;
        }
        for (int i = 1; i <= result; i++) {
    
            // The first line initializes 
            if (i >= nums[0]) {
    
                dp[0][i] = nums[0];
            }
        }
        /** 0 1 2 3 4 5  Total capacity  * 0 0 1 1 1 1 1 * 1 0 * 2 0 * 3 0 *  The first  *  A few  *  individual  */
        for (int i = 1; i < n; i++) {
    
            for (int j = 1; j <= result; j++) {
    
                if (dp[i - 1][j] == result) {
    
                    return true;
                }
                if (nums[i] + dp[i - 1][j] > result) {
    
                    // If the current value is not included 
                    // The current value is still the original 
                    dp[i][j] = dp[i - 1][j];
                } else if (nums[i] + dp[i - 1][j] < result) {
    
                    // If the current sum is less than result, It can be put in 
                    if (j >= nums[i]) {
    
                        // If the capacity > The number of , Can be put in 
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                    } else {
    
                        // If the current position cannot be put down, use the original 
                        dp[i][j] = dp[i - 1][j];
                    }
                } else {
    
                    // If you encounter just , Full of , Go straight back .
                    return true;
                }
                for (int k = 0; k < n; k++) {
    
                    for (int l = 0; l <= result; l++) {
    
                        System.out.print(dp[k][l] + " ");
                    }
                    System.out.println();
                }

            }
        }
        return false;
    }

    public static void main(String[] args) {
    
// System.out.println(new CanPartition().canPartition(new int[]{1, 2, 3, 4, 5, 6, 7}));
        System.out.println(new CanPartition().canPartition(new int[]{
    1, 1}));
// System.out.println(new CanPartition().canPartition(new int[]{2, 2, 3, 5}));
// System.out.println(new CanPartition().canPartition(new int[]{1, 5, 11, 5}));
    }
}