The ergodic order relation between “complete backpack” and “01 backpack” is deduced from the mathematical perspective

preface

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

In many backpack problem “01 backpack problem” is the most central, so I suggest you read carefully firstBackpack problem number oneThen read this article.

One of the 01 backpack “one-dimensional space optimization” is to focus on mastering.

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 order it is arranged (update every few 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

There are NNN items and a backpack with a capacity of CCC, with an infinite number of items for 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].

Figure out which items to put into the backpack so that the total cost of these items does not exceed the backpack capacity and the total value is maximum.

In fact, based on the 0-1 knapsack problem, each item can be selected multiple times (as capacity allows).

Example 1:

Input: N = 2, C = 5, V = [1,2], w = [1,2] Output: 5 Explanation: Select one item 1 and two items 2 to maximize the value.Copy the code

Conventional method

We can directly use the “state definition” of the 01 backpack:

$dp[i][j]$Representative before consideration
$i$One item into a capacity of
$j$The backpack can get the maximum value.

Since each item can be selected multiple times, the value for a dp[I][j]dp[I][j]dp[I][j] should be the maximum of all the following possible schemes:

• Select 0 item III for maximum value, i.e. Dp [I −1][J] DP [I-1][J] DP [I −1][J]dp[I −1][J]

• Choose 1 item iii maximum value, that is, dp [I – 1] [j – v [I]] [I] dp + w [I – 1] [j – v [I]] [I] dp + w [I – 1] [j – v [I]] + w [I]

• The great value of the option 2 item iii, that is, dp [I – 1] [j ∗ v [I]] – 2 + 2 ∗ w [I] dp [I – 1] [j – 2 * v [I]] [I] dp + 2 * w [I – 1] [j ∗ v [I]] – 2 + 2 ∗ w [I]

  .

• Choose the maximum value of k item iii, dp [I – 1] [j ∗ v [I]] – k + k ∗ w [I] dp [I – 1] [I]] [j – k * v * w + k [I] dp [I – 1] [j ∗ v [I]] – k + k ∗ w [I]

Thus, we can conclude that the “state transition equation” is:

Code:

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[N][C + 1];
        
        // Preprocess the first item
        for (int j = 0; j <= C; j++) {
            // Obviously when there is only one item, you can choose as many items as capacity allows
            int maxK = j / v[0];
            dp[0][j] = maxK * w[0];
        }
        
        // Dispose of the remaining items
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // select 0 item I without considering item I
                int n = dp[i - 1][j];
                // Consider the case of item I
                int y = 0;
                for (int k = 1 ;; k++) {
                    if (j < v[i] * k) {
                        break;
                    }
                    y = Math.max(y, dp[i - 1][j - k * v[i]] + k * w[i]); } 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, but each transfer requires enumerating the number of current items at most C times (weight is the minimum value 1), so the overall complexity is O(N∗C∗C)O(N * C * C)O(N∗C∗C).
• Space complexity: O(N∗C)O(N * C)O(N∗C)

Scroll to the array

By looking at our “state transition equation”, we can see that we only rely on DP [I −1][x]dp[I][I][X]dp[I −1][x] when updating a certain DP [I][x] DP [I −1][x].

So we can optimize the space to O(C)O(C)O(C) by “scrolling arrays” like the 01 knapsack.

Code:

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[2][C + 1];
        
        // Preprocess the first item
        for (int j = 0; j <= C; j++) {
            // Obviously when we only have one item, we can choose as many items as capacity allows
            int maxK = j / v[0];
            dp[0][j] = maxK * w[0];
        }
        
        // Dispose of the remaining items
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // select 0 item I without considering item I
                int n = dp[(i - 1) &1][j];
                // Consider the case of item I
                int y = 0;
                for (int k = 1 ;; k++) {
                    if (j < v[i] * k) {
                        break;
                    }
                    y = Math.max(y, dp[(i - 1) &1][j - k * v[i]] + k * w[i]);
                }
                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, but each transfer requires enumerating the number of current items at most C times (weight is the minimum value 1), so the overall complexity is O(N∗C∗C)O(N * C * C)O(N∗C∗C).
• Space complexity: O(N∗C)O(N * C)O(N∗C)

One-dimensional space optimization

We know that in 01 knapsack, the most important is the “one-dimensional space optimization” solution.

The reason why 01 knapsack can use the “one-dimensional space optimization” solution is because when we start to deal with the
$i$The array stores items that have already been processed
$i – 1$The state value of the item.

Then, in combination with the “from large to small” traversal order of our capacity dimensions, we can ensure that when updating a certain state, the required state values will not be overwritten.

Therefore, the state transition equation of 01 knapsack problem is:

At the same time, the traversal order of the capacity dimension is from large to small.

PS. If you don’t quite understand the above, perhaps because you “haven’t learned” or “kind of forgot” the 01 backpack problem, Mitsuha strongly recommends that you study/review the 01 backpack problem first.

The “full backpack” differs from the “01 backpack” in that each item can be selected multiple times.

So you might see this explanation somewhere else:

“01 knapsack traverses the capacity dimension” from large to small “meaning that each item can only be selected one, while full knapsack traverses the capacity dimension” from small to large “meaning that each item can be selected multiple times.

Such an explanation actually makes use of people’s abstract thinking, but the feeling is not necessarily right.

Next, we prove from the “mathematical” point of view why modifying the traversal order of 01 knapsack can correctly solve the complete knapsack problem.

Dp [I][j]dp[I][j]dp[I][j]dp[I][j]

Dp [I][j] DP [I][j] [J]dp[I][j] meaning: under the condition of capacity permitting, for the third item, we can not choose, can choose 1 times, can choose 2 times… , you can choose KKK times…

Then we through substitution, see dp [I] [j – v [I]] dp [I] [j – v [I]] dp [I] [j – v [I]] what is the content:

It may be hard to see the connection just by looking at the formula, but Mitsuha marks the same part:

To sum up.

• The state transition equation of 0-1 knapsack problem is:

Due to the calculation
$dp[i][j]$Rely on
$dp[i – 1][j – v[i]]$.

Therefore, we need to make sure that when we change to “one-dimensional spatial optimization”
$dp[j – v[i]]$The value of the previous row is stored, that is, ensure
$dp[j – v[i]]$It hasn’t been updated yet, so the traversal direction is from large to small.

• The state transition equation of the complete knapsack problem is:

Due to the calculation
$dp[i][j]$Rely on
$dp[i][j – v[i]]$.

Therefore, we need to make sure that when we change to “one-dimensional spatial optimization”
$dp[j – v[i]]$The value of the current row is stored, that is, ensure
$dp[j – v[i]]$Has been updated, so the traversal direction is from small to large.

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 = 0; j <= C; j++) {
                // select 0 item I without considering item I
                int n = dp[j];
                // Consider the case of item I
                int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; 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 we studied the “complete knapsack” problem in dynamic programming/knapsack problem.

Formally, we only need to change the ergodic direction of “capacity dimension” in the “one-dimensional space optimization” solution of 01 knapsack problem from “from large to small” to “from small to large” to solve the complete knapsack problem.

But the essence is that they rely on different grids for state transitions:

• The 01 knapsack relies on “the grid directly above the previous row” and “the grid to the left of the previous row”.

• The full knapsack relies on “the grid directly above the previous row” and “the grid to the left of the row”.

In addition, we can find that the time complexity of solving the “complete knapsack” problem can be reduced from O(N∗C∗C)O(N *C *C)O(N∗C ∗C) to O(N∗C)O(N*C)O(N∗C) through the “one-dimensional space optimization” method.

This is why Mitsuha has been emphasizing the “one-dimensional spatial optimization” of the 01 knapsack problem as the basis for almost all knapsack problems.

Backpack Problem (Table of Contents)

1. Knapsack: Knapsack problem first lecture

   1. 01 Backpack: Backpack problem In Lecture 2

   2. 01 Backpack: Backpack problem Lecture 3

2. Complete backpack: this piece

   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. Lesson 17: The Backpack Problem

   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