【 Backpack problem series 】 two, abstract backpack problem

Abstract knapsack problem

[B].

Given a non-empty array containing only positive integers. Is it possible to split this array into two subsets so that the sum of the elements in the two subsets is equal? Note: No more than 100 elements in each array Size no more than 200 Example 1: Input: [1, 5, 11, 5] Output: true Explanation: Arrays can be split into [1, 5, 5] and [11]. Example 2: Input: [1, 2, 3, 5] Output: false Explanation: An array cannot be split into two elements and equal subsets.Copy the code

[D].

Subject analysis

• Two elements and equal subsets, i.e. Sum- Sum [1]= Sum [1]= Sum [2]=Sum/2 for each subset, and all values are integers
• So we can rule out the case where the sum of all elements is odd
• The next question seems to be an easy oneAbstract as knapsack problemthe
  • Can you find a situation where there is a fixed number of n items with a total value? Can you find a situation where the selected items meet the items and are total/2

Idea 1: Dynamic planning

• (TLE) (TLE) (TLE) (TLE

• When it is difficult to imagine the DP equation at the first time, recursive method can be considered for parameter confirmation

• When solving recursively, if solving forward, add one item at a time, and then determine whether the previous I can meet the maximum value of the requirement j (maximum value does not exceed j)

• Therefore, the equation DP [I][j] can be defined to mean that the use of the first I elements does not exceed the maximum value of j

• dp[i][j] = Math.max(dp[i – 1][j], j >= val ? dp[i – 1][j – val] + val : 0)

public boolean canPartition(int[] nums) {
            int total = 0;
            for (int n : nums
            ) {
                total += n;
            }
            //corner case
            if (total % 2! =0) {
                return false;
            }
            int target = total / 2 + 1;
            int[][] dp = new int[nums.length][target];
            // Initializes the boundary case, taking only all cases of the first element
            for (int i = 0; i < target; i++) {
                dp[0][i] = nums[0] < i ? nums[0] : 0;
            }
            for (int i = 1; i < nums.length; i++) {
                int val = nums[i];
                for (int j = 0; j < target; j++) {
                    // Select or unselect two states
                    dp[i][j] = Math.max(dp[i - 1][j], j >= val ? dp[i - 1][j - val] + val : 0); }}return dp[nums.length - 1][target - 1] == target - 1;
        }
Copy the code

Time complexity O(n+ N *total)

The optimization method of other dimensions is very similar to knapsack problem series 1

Optimize a dimension abstraction into odd and even

public boolean canPartition(int[] nums) {
            int total = 0;
            for (int n : nums
            ) {
                total += n;
            }
            //corner case
            if (total % 2! =0) {
                return false;
            }
            int target = total / 2 + 1;
            int[][] dp = new int[2][target];
            // Initializes the boundary case, taking only all cases of the first element
            for (int i = 0; i < target; i++) {
                dp[0][i] = nums[0] < i ? nums[0] : 0;
            }
            for (int i = 1; i < nums.length; i++) {
                int val = nums[i];
                for (int j = 0; j < target; j++) {
                    // Select or unselect two states
                    dp[i & 1][j] = Math.max(dp[(i - 1) & 1][j], j >= val ? dp[(i - 1) & 1][j - val] + val : 0); }}return dp[(nums.length-1) &1][target - 1] == target - 1;
        }
Copy the code

Optimize the abstraction of two dimensions into one dimension

public boolean canPartition(int[] nums) {
            int total = 0;
            for (int n : nums
            ) {
                total += n;
            }
            //corner case
            if (total % 2! =0) {
                return false;
            }
            int target = total / 2 + 1;
            int[] dp = new int[target];
            for (int i = 0; i < nums.length; i++) {
                int val = nums[i];
                for (int j = target - 1; j >= 0; j--) {
                    int no = dp[j];
                    // select item I
                    int yes = j >= val ? dp[j - val] + val : 0; dp[j] = Math.max(no, yes); }}return dp[target - 1] == target - 1; }}Copy the code

【 References 】

• Gong Shui backpack problem sorting
• Related Leetcode links