preface

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

On this happy Friday, we are officially blowing the whistle on the DP backpack problem 🎉 🎉 ~

We just finished our first series on dynamic programming: the path problem.

If you haven’t seen it yet, I highly recommend you take the time to study it. Because the “empirical solutions” and “technical solutions” taught in the path problem will be throughout all of our subsequent “dynamic programming topics” series.

As usual, I ended the article with a list of topics RELATED to the backpack problem that I had 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 ~

Nature of knapsack problem

Knapsack problem is a very classic problem in “dynamic programming”. Knapsack problem belongs to combinatorial optimization in essence.
N P NP Completely problematic.

If you don’t know what the “NPNP complete problem” is, it doesn’t matter, it doesn’t affect you to solve the knapsack problem.

You can think of “NPNPNP complete problems” as simply “problems that cannot be solved directly”.

For example, the problem of “factoring prime factors” cannot be solved according to specific logic like the four operations (addition, subtraction, multiplication and division).

The solution can only be solved by “exhaustive” + “verification”.

Since it is essentially an unavoidable “exhaustive” problem, it will naturally be associated with “dynamic programming”. In fact, knapsack problem also meets the requirements of “no aftereffect”.

This is the fundamental reason why “knapsack problems” are solved using “dynamic programming”.

If we abstract the model according to the common “knapsack problem” question type, “knapsack problem” probably corresponds to the following kind of problem:

General refers to a kind of “given value and cost”, at the same time “limited decision rules”, under such conditions, how to maximize the value of the problem.

Today we are going to talk about the 01 backpack problem in the backpack problem.

“01 knapsack” refers to how to maximize the total value of selected items with a given value and volume (corresponding to “given value and cost”) and a specified capacity (corresponding to “restricted decision rules”).

Topic describes

There are NNN items and a backpack with a capacity of VVV. There is one and only one of each item.

The volume of item III is V [I]v[I]v[I]v[I] and the value is W [I]w[I]w[I] W [I].

Solve which items to put into the backpack so that the total volume of these items does not exceed the backpack capacity, and the total value of the maximum.

Example 1:

Enter N =3, C = 4, v = [4.2.3], w = [4.2.3] output:4Explanation: Choose only the first item to maximize value.Copy the code

Example 2:

Enter N =3, C = 5, v = [4.2.3], w = [4.2.3] output:5Explanation: Instead of choosing the first item, choose the second and third items to maximize value.Copy the code

Solution C + dp [N] [1]

Even if we have never dealt with knapsack problems, we can use the “trick solutions” we learned from the path problems.

If we were to design a DFS function to enumerate all the schemes, it would look something like this:

int dfs (int[] v, int[] w, int i, int c);
Copy the code

VVV and WWW correspond to the input “item volume” and “item value”, which belong to the invariable parameters and need not be considered.

While III and CCC stand for “what item is currently enumerated to” and “current remaining capacity” respectively.

The return value is the answer to our question: maximum value.

So we can abstract out our dp array based on the variable parameter and return value:

A two-dimensional array, with one dimension representing the current “what items are currently enumerated” and another dimension representing the “current remaining capacity”, assembles the “maximum value”.

According to the DP array, it is not difficult to get the state definition:

Before considering
i i The use capacity of one item does not exceed
C C Condition the backpack under maximum value.

Once the state definition is in place, we derive the state transition equation from the “last-step” choice.

Without losing generality, we just have to think about theta
i i How to choose items, for the first
i i We have two choices: “choose” and “don’t choose”.

Combined with our “state definition”, the “maximum value” of the “no” option is well determined:

“Not to choose” actually means
d p [ i – 1 ] [ c ] dp[i – 1][c] Is equivalent to considering only the former
i – 1 i – 1 Item, the current capacity is
c c In the case of maximum value.

Similarly, if we pick number one
i i One item means consumed
v [ i ] v[i] The backpack capacity is obtained
w [ i ] w[i] Value, then leave it to the former
i – 1 i – 1 The backpack capacity of one item is only left
c – v [ i ] c – v[i] . The maximum value is zero
d p [ i – 1 ] [ c – v [ i ] ] + w [ i ] dp[i – 1][c – v[i]] + w[i] .

Of course, I chose Article III with a prerequisite: “Current remaining knapsack capacity” – – Geqslant ⩾ “volume of items”.

The maximum value between “select” and “not select” is the “maximum value of the backpack” under the condition that “the use capacity of the first three items is not more than CCC”.

Then, the “state transition equation” can be written:

Code:

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[N][C+1];
        // Handle the "consider the first item" case first
        for (int i = 0; i <= C; i++) {
            dp[0][i] = i >= v[0]? w[0] : 0;
        }
        // Reprocess the "consider the rest" case
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < C + 1; j++) {
                // do not select this item
                int n = dp[i-1][j]; 
                // Select this item if "Remaining capacity" is greater than or equal to "Item volume"
                int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0; dp[i][j] = Math.max(n, y); }}return dp[N-1][C]; }}Copy the code
  • Time complexity: A total of N∗CN * CN∗C states need to be transferred, and the complexity is O(N∗C)O(N * C)O(N∗C)
  • Space complexity: O(N∗C)O(N * C)O(N∗C)

Dp [2], [C + 1) solutions

From the “transfer equation”, we know that only some values in rows I − 1i-1i −1 are needed to compute the row III cell.

That is, the calculation of “certain row” depends only on “previous row”.

So you can store the intermediate result with an array of only two rows, alternating between row 0 and row 1 depending on whether the row number currently computed is even or odd.

This spatial optimization method is called “scrolling arrays,” and I shared it with you in lecture 4 on paths.

This spatial optimization method is highly recommended because there is no mental difficulty in changing it.

Just change the dimension representing the row to 2 and change everything that uses the row dimension from
i i to
i % 2 i\%2 or
i & 1 i\&1 Can (more recommended use
i & 1 i\&1 & is more stable than % on machines with different CPU architectures.

Code:

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[2][C+1];
        // Handle the "consider the first item" case first
        for (int i = 0; i < C + 1; i++) {
            dp[0][i] = i >= v[0]? w[0] : 0;
        }
        // Reprocess the "consider the rest" case
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < C + 1; j++) {
                // do not select this item
                int n = dp[(i-1) &1][j]; 
                // Select this item
                int y = j >= v[i] ? dp[(i-1) &1][j-v[i]] + w[i] : 0;
                dp[i&1][j] = Math.max(n, y); }}return dp[(N-1) &1][C]; }}Copy the code
  • Time complexity: A total of N∗CN * CN∗C states need to be transferred, and the complexity is O(N∗C)O(N * C)O(N∗C)
  • Space complexity: O(C)O(C)O(C)

Dp [C + 1) solutions

In fact, we can go ahead and optimize the space so that only the dimensions that represent “remaining capacity” remain.

Look again at our “transfer equation” :

It is not difficult to find that when solving the value of row III grid, not only the I − 1i-1I −1 line is relied on, It also explicitly relies on only the CCC cell of row I − 1i-1I −1 and the C − V [I] C-V [I] C − V [I] [I]c− V [I] (i.e., the case where item III is not selected and the case where item III is selected).

In other words, it depends only on the position of the previous grid and the position to the left of the previous grid.

Therefore, if we change the order of solving row III cells from “000 to CCC” to “CCC to 000”, we can compress the 2-row array into one line (converting to a 1-dimensional array).

The space complexity of doing this is the same as the space complexity of the “scrolling array” optimization. But it is still meaningful, and such “one-dimensional space” optimization, is the basis of solving other knapsack problems, need to focus on mastering.

Code:

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                // do not select this item
                int n = dp[j]; 
                // Select this item
                inty = dp[j-v[i]] + w[i]; dp[j] = Math.max(n, y); }}returndp[C]; }}Copy the code
  • Time complexity: A total of N∗CN * CN∗C states need to be transferred, and the complexity is O(N∗C)O(N * C)O(N∗C)
  • Space complexity: O(C)O(C)O(C)

conclusion

Today, Mitsuha explains what knapsack problems are, what the nature of knapsack problems is, and why knapsack problems need dynamic programming to solve them…

Among them, “01 backpack” problem is the core of many backpack problems.

We optimized from the “conventional solution” of the 01 knapsack to the “rolling array solution” and then to the “one-dimensional space optimization solution”.

It is important to understand the one-dimensional space optimization solution, which will be the basis for other knapsack problems.

Other knapsack problems to a certain extent can be transformed into “01 knapsack” to solve, or according to the transfer equation of “01 knapsack” to slightly modify the solution.

Backpack Problem (Table of Contents)

  1. 01 Backpack: This piece

    1. 01 Backpack: Backpack problem In Lecture 2

    2. 01 Backpack: Backpack problem Lecture 3

  2. 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

  3. Multiple backpacks: Lecture 8 on the Backpack Problem

  4. Multiple backpacks

    1. 【 I 】 Multiple Knapsacks: The Knapsack Problem lecture 9

    2. Multiple Knapsack (Optimization) : Knapsack problem lecture 10

  5. Mixed knapsack: The knapsack problem lecture 11

  6. Grouping knapsack: Lecture 12 of the knapsack problem

    1. Group packs: Backpack problem Lecture 13

  7. Multidimensional knapsack

    1. Multidimensional knapsack: The Knapsack problem Lecture 14

    2. Multi-dimensional knapsack: The knapsack problem lecture 15

  8. The Tree Backpack: Lecture 16 on the Backpack Problem

    1. A tree backpack

    2. A tree backpack

  9. Knapsack solution number

    1. 【 典 型 范 例 2 】 The number of options is the same as the number of options

  10. Backpack for specific programs

    1. 【 practice 】 backpack to find a specific plan

  11. Generalization backpack

    1. 【 exercise 】 Generalization backpack