【 backpack problem no. 3 讲】 From "no more than" to "just", from another Angle to understand the backpack problem

preface

Today is the third day of our presentation on the knapsack problem in dynamic programming.

Of all the backpack problems, “01 backpack problem” is the most central, so I recommend you read the backpack problem first lecture carefully before reading this article.

In addition, AT the end of the article, I listed the related topics about the backpack problem that I sorted out.

I will explain the backpack problem in the arranged order (update every 2-3 days to make sure you digest it).

You can also try to do it first, you are also welcome to leave a message to me, you feel related to backpack DP type topic ~

Topic describes

This is 416 on LeetCode. Split and subset, Medium difficulty.

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:

There are no more than 100 elements in each array
The size of the array cannot exceed 200

Example 1:

Input: [1, 5, 11, 5] Output: true Explanation: Arrays can be split into [1, 5, 5] and [11].Copy the code

Example 2:

Input: [1, 2, 3, 5] Output: false Explanation: An array cannot be split into two elements and equal subsets.Copy the code

Fundamental analysis

The basic analysis of “abstracting the original problem into 01 knapsack problem” was discussed in the last lecture

The problem in this section is: how to change the method of “indirect solution” to “direct solution”, and learn why it is possible to do so, and whether there are commonalities between these methods…

Direct solution

Let’s start by reviewing the “state definition” and “transition equation” used in the previous section.

State definition:

F [I][j]f[I][j]f[I][j]f[I][j] represents that the sum of the selected numbers does not exceed the maximum value of JJJ when considering the first three values.

Transfer equation:

But the question is not, “What is the maximum value?” it is, “Can we get the maximum value?”

Therefore, we can modify the state definition of 01 knapsack to make it directly related to our answer:

F [I][j]f[I][j]f[I][j] represents whether the sum of the selected numbers is exactly JJJ considering the previous iii values.

In this case, DPDPDP array stores “Boolean type” moving gauge value.

The corresponding state transition equation can be adjusted as:

∨∨ means “or” in logic.

The new transfer equation represents: f[I][j]f[I][j]f[I][j]f[I][j] (considering the first iii values, the sum of the selected numbers is exactly JJJ) is true. The following two schemes must be met, at least one of which is TrueTrueTrue:

1. $f[i-1][j]$ (don’t choose the first $i$ The sum of the selected numbers is exactly $j$ ) for $true$

2. $f[i-1][j-nums[i]]$ (choose the first $i$ The sum of the selected numbers is exactly $j$ ) for $true$

So far, using the basic idea of the 01 knapsack, we have modified the “state definition” to relate it directly to the answer, and then adjusted our “transition equation” according to the new “state definition.”

But it’s not over yet.

When we modify the “state definition” of a model, we need to consider modifying the “initialization” state in addition to adjusting the “transition equation.”

Consider that the DPDPDP arrays we create store Boolean values with initial FalseFalse values, which means that no matter how we transfer them, it is impossible to generate a trueTrueTrue, and ultimately all states will still be FalseFalse.

In other words, we also need a valid value trueTruetrue to help recurse.

Usually we use the first line to initialize valid values.

F [0][nums]]=truef[0][nums[0]] =truef[0][nums[0]] =true

F [0][nums[0]]=truef[0][nums[0]] =truef[0][nums[0]] =true indicates that only knapsacks with the capacity of NUMs [0]nums[0]nums[0] meet the requirement of “exactly”.

But we can’t be sure that NUMs [0] NUMs [0]nums[0] won’t exceed our “maximum backpack” capacity (that is, the case where the first item is too big to ever fit in the backpack).

So we’re going to get valid values by processing the next row, right? Or do you prioritize things first?

In fact, one trick here is that we add a “no item” case to the discussion.

Previously our state definition was f[I][j]f[I][j]f[I][j] stands for all items before subscript III. Now we can add the case without considering any items, which is to change the “item number” from 0 to 1.

For 🌰, originally we f [0] [x] f [0] [x] f [0] [x] represent only consider the first item, f [1] [x] f [1] [x] f [1] [x] representatives consider the first and second items; Adjusted our f [0] [x] f [0] [x] f [0] [x] representative does not consider any item, f [1] [x] f [1] [x] f [1] [x] represent only consider the first item…

This technique essentially uses the idea of the sentinel.

With that analysis in mind, and the code base we covered last time, it’s easy to write code.

Although the state definition and transition equation are changed, there are still several implementation methods including “conventional solution”, “rolling array optimization” and “one-dimensional space optimization”. Let’s go through this really quickly.

Conventional method

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;

        // The sum of "equal sum subsets" must be half of the sum
        int sum = 0;
        for (int i : nums) sum += i;
        int target = sum / 2;

        // If the sum is odd, it cannot be divided into two equal sum subsets.
        if (target * 2! = sum)return false;

        // f[I][j] represents a scenario where the value of the previous I items is "exactly" j
        boolean[][] f = new boolean[n+1][target+1];
        f[0] [0] = true;
        for (int i = 1; i <= n; i++) {
            int t = nums[i-1];
            for (int j = 0; j <= target; j++) {
                // do not select this item
                boolean no = f[i-1][j];
                // select this item
                boolean yes = j >= t ? f[i-1][j-t] : false; f[i][j] = no | yes; }}returnf[n][target]; }}Copy the code

Time complexity: TargettargettarGet is half of the array sum, NNN number of array elements. Denotes that a total of N ∗targetn * targetn∗target states need to be transferred, and the complexity is O(n∗target)O(n * target)O(n∗target)
Space complexity: O(n∗target)O(n * target)O(n∗target)

Scroll to the array

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;

        // The sum of "equal sum subsets" must be half of the sum
        int sum = 0;
        for (int i : nums) sum += i;
        int target = sum / 2;

        // If the sum is odd, it cannot be divided into two equal sum subsets.
        if (target * 2! = sum)return false;

        // f[I][j] represents a scenario where the value of the previous I items is "exactly" j
        // Change the item dimension to 2
        boolean[][] f = new boolean[2][target+1];
        f[0] [0] = true;
        for (int i = 1; i <= n; i++) {
            int t = nums[i-1];
            for (int j = 0; j <= target; j++) {
                // do not select this item
                boolean no = f[(i-1) &1][j];
                // select this item
                boolean yes = j >= t ? f[(i-1) &1][j-t] : false;
                f[i&1][j] = no | yes; }}return f[n&1][target]; }}Copy the code

Time complexity: TargettargettarGet is half of the array sum, NNN number of array elements. Denotes that a total of N ∗targetn * targetn∗target states need to be transferred, and the complexity is O(n∗target)O(n * target)O(n∗target)
O(Target)O(target)O(target)

One-dimensional space optimization

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;

        // The sum of "equal sum subsets" must be half of the sum
        int sum = 0;
        for (int i : nums) sum += i;
        int target = sum / 2;

        // If the sum is odd, it cannot be divided into two equal sum subsets.
        if (target * 2! = sum)return false;

        // Remove the item dimension
        boolean[] f = new boolean[target+1];
        f[0] = true;
        for (int i = 1; i <= n; i++) {
            int t = nums[i-1];
            for (int j = target; j >= 0; j--) {
                // do not select this item
                boolean no = f[j];
                // select this item
                boolean yes = j >= t ? f[j-t] : false; f[j] = no | yes; }}returnf[target]; }}Copy the code

Time complexity: TargettargettarGet is half of the array sum, NNN number of array elements. Denotes that a total of N ∗targetn * targetn∗target states need to be transferred, and the complexity is O(n∗target)O(n * target)O(n∗target)
O(Target)O(target)O(target)

conclusion

Today we did “416. Segmentation and subsets” again, but from a different Angle:

By modifying 01 knapsack “state definition” and “transfer equation” to achieve “direct solution”.

But is that a particular problem?

Not really. Instead, it’s a generalizable property of the backpack problem:

We can change the “state definition” of a knapsack problem from a maximum of XX capacity to a knapsack capacity of exactly XX, and then set the “valid value construction”, that is, the subscript of the item to start from 1, and set dp[0][0] DP [0][0] DP [0][0]dp[0][0] as the initial value.

This is another kind of “knapsack problem” that doesn’t correspond to “value maximization”, but rather “maximization/specific value”. The “backpack problem” is also common.

We need to master ~

Backpack Problem (Table of Contents)

Knapsack: Knapsack problem first lecture
1. 01 Backpack: Backpack problem In Lecture 2
2. 01 Backpack
Complete knapsack: Lecture 4 of the knapsack problem
1. Complete backpack: The backpack problem lecture 5
2. The whole backpack problem Lecture 6
3. Complete knapsack: Knapsack problem Lecture 7
Multiple backpacks: Lecture 8 on the Backpack Problem
Multiple backpacks
1. 【 I 】 Multiple Knapsacks: The Knapsack Problem lecture 9
2. Multiple Knapsack (Optimization) : Knapsack problem lecture 10
Mixed knapsack: The knapsack problem lecture 11
Grouping knapsack: Lecture 12 of the knapsack problem
1. Group packs: Backpack problem Lecture 13
Multidimensional knapsack
1. Multidimensional knapsack: The Knapsack problem Lecture 14
2. Multi-dimensional knapsack: The knapsack problem lecture 15
The Tree Backpack: Lecture 16 on the Backpack Problem
1. Lesson 17: The Backpack Problem
2. A tree backpack
Knapsack solution number
1. 【典型范例 2 】 The number of options is the same as the number of options
Backpack for specific programs
1. 【 practice 】 backpack to find a specific plan
Generalization backpack
1. 【 exercise 】 Generalization backpack

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

【 backpack problem no. 3 讲】 From “no more than” to “just”, from another Angle to understand the backpack problem

preface

Topic describes

Fundamental analysis

Direct solution

Conventional method

Scroll to the array

One-dimensional space optimization

conclusion

Backpack Problem (Table of Contents)

【 backpack problem no. 3 讲】 From “no more than” to “just”, from another Angle to understand the backpack problem

preface

Topic describes

Fundamental analysis

Direct solution

Conventional method

Scroll to the array

One-dimensional space optimization

conclusion

Backpack Problem (Table of Contents)

Related Posts

MySQL Advanced – Query and slow query log analysis

Java source code -JDK 1.8 HashMap key source code section analysis

Linux Docker installation, boot from the boot, set up the domestic image, install Nginx, mapping Nginx files