How to abstract the original problem into "01 backpack" problem

preface

Today is the second 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

Most knapsack problems test our ability to “model”, or turn a problem into a knapsack problem.

Can we divide an array into two equal-sum subsets?

The problem is equivalent to whether you can pick a number of elements from an array so that the sum of the elements is equal to half of the sum of all the elements.

A. backpack problem B. backpack problem C. backpack problem D. backpack problem

Our backpack capacity is $target=sum/2$ , the “value” and “cost” of each array element are its numerical size, asking whether we can fill the backpack.

Convert to 01 knapsack

Since each number (array element) can only be selected once, and each number is selected or not for “value” and “cost”, the problem is also related to “maximum value”.

This can be done using a model of the “01 backpack”.

When we determine that a problem can be transformed into “01 knapsack”, we can directly apply the state definition of “01 knapsack” to solve.

Note that the point of our accumulation of DP models is that we can quickly get reliable “state definitions”.

inRouting problemI taught you the general DP technique, but that is based on the fact that we have never seen a DP problem before, and for some DP problems that we have seen, we should apply (or fine-tune) the model “state definition” directly.

Let’s directly apply the state definition of “01 backpack” :

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.

Once the state definition is in place, each number can be selected either “select” or “do not select” using our last-step analysis.

Therefore, it is not difficult to obtain the state transition equation:

Code:

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;

        int[][] f = new int[n][target + 1];
        // First deal with the case of item 1
        for (int j = 0; j <= target; j++) {
            f[0][j] = j >= nums[0]? nums[0] : 0;
        }

        // Reprocessing takes into account the rest of the items
        for (int i = 1; i < n; i++) {
            int t = nums[i];
            for (int j = 0; j <= target; j++) {
                // do not select item I
                int no = f[i-1][j];
                // select item I
                int yes = j >= t ? f[i-1][j-t] + t : 0; f[i][j] = Math.max(no, yes); }}// If the maximum value is equal to target, it can be split into two equal sum subsets.
        return f[n-1][target] == 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

In the last lecture we talked about “01 knapsack” has two ways of space optimization.

The coding implementation of one optimization method is very fixed, and it only needs to fix the “item dimension”.

Code:

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 (target * 2! = sum)return false;

        // Change the item dimension to 2
        int[][] f = new int[2][target + 1];
        // First deal with the case of item 1
        for (int j = 0; j <= target; j++) {
            f[0][j] = j >= nums[0]? nums[0] : 0;
        }

        // Reprocessing takes into account the rest of the items
        for (int i = 1; i < n; i++) {
            int t = nums[i];
            for (int j = 0; j <= target; j++) {
                // Discard item I and add &1 to item dimension usage
                int no = f[(i-1) &1][j];
                // Select the I item and add "&1" to the item dimension.
                int yes = j >= t ? f[(i-1) &1][j-t] + t : 0;
                f[i&1][j] = Math.max(no, yes); }}// If the maximum value is equal to target, it can be split into two equal sum subsets.
        // Add "&1" to the use of item dimensions
        return f[(n-1) &1][target] == 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

In fact, we can continue with spatial optimization: only the dimensions representing “remaining capacity” are retained, and the capacity traversal direction is changed to “large to small.”

Code:

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
        int[] f = new int[target + 1];
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            // Change the "capacity dimension" to traversal from large to small
            for (int j = target; j >= 0; j--) {
                // do not select item I
                int no = f[j];
                // select item I
                int yes = j >= t ? f[j-t] + t : 0; f[j] = Math.max(no, yes); }}// If the maximum value is equal to target, it can be split into two equal sum subsets.
        returnf[target] == 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 have applied the “01 backpack” we learned yesterday.

It can be found that the difficulty of this problem lies in the abstraction of the problem, and the main investigation is how to convert the original problem into a “01 backpack” problem.

In fact, whether DP or graph theory, most have models or algorithms for a particular problem.

The difficulty is translating the problem into our model.

As for how to develop their “problem abstraction ability”?

First of all, we usually need to accumulate a certain amount of brush questions, and make a summary of the “key points of the transformation problem”.

In this case, for example, one of the key points in transforming the “01 knapsack problem” is that we need to think of the problem of “dividing equal and subset” as equivalent to the problem of “choosing a number of numbers in an array so that the sum is a particular value”.

expand

But there is still a “small problem” with this problem.

Is that we get the answer through judgment in the end.

Determine whether “equal and subset” can be divided by determining whether the maximum value obtained is equal to targettargettarget.

Although it is completely logical, it always gives us a sense of “indirect solution”.

This “indirect solution” feeling is mainly due to the fact that we didn’t make any changes to the “state definition” and “initialization” of the “01 backpack”.

But in fact, we can use the “01 knapsack” idea to “directly solve”.

So we’re going to do this problem again in the next lecture.

But it is to “another Angle” “01 backpack” thinking to solve.

Stay tuned ~

Backpack Problem (Table of Contents)

Knapsack: Knapsack problem first lecture
1. 01 Backpack
2. 01 Backpack: Backpack problem Lecture 3
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.

How to abstract the original problem into “01 backpack” problem

preface

Topic describes

Fundamental analysis

Convert to 01 knapsack

Scroll to the array

One-dimensional space optimization

conclusion

expand

Backpack Problem (Table of Contents)

How to abstract the original problem into “01 backpack” problem

preface

Topic describes

Fundamental analysis

Convert to 01 knapsack

Scroll to the array

One-dimensional space optimization

conclusion

expand

Backpack Problem (Table of Contents)

Related Posts

Check out the high imitation app projects on Github, Weibo, wechat and so on

Java class loading mechanism (I) – Just finish reading these two articles

Java base collection queue-LinekdList