Dynamic programming chapter 5:01 knapsack problem and complete knapsack problem

Still moving gauge five – part analysis of a wave.

The first step is to determine what the DP array and subscripts mean

For the backpack problem, there is a way to write it, which is to use a two-dimensional array, that is, DP [I][j] represents the maximum sum of the value of the backpack with capacity J, which is arbitrarily taken from the items with subscript [0-i].

If you just look at the definition of a two-dimensional array, you’ll get a little confused. Look at the following diagram:

So to keep in mind what this dp array means, the next few steps are going to be around what this DP array means, and if you’re confused, let’s review what I stands for and what J stands for.

The second step is to determine the recursive formula

Let’s review the meaning of dp[I][j] : take any item with subscript [0-i] and put it into a backpack with capacity J. What is the maximum sum of the value?

So you can derive dp[I][j] in two directions,

1. It can be deduced from dp[i-1][J], that is, the backpack capacity is J, and the maximum value of item I is not contained in it, then DP [I][j] is DP [i-1][J].
2. Derived from DP [i-1][j-weight [I]], dp[i-1][J-weight [I] is the maximum value of item I without backpack capacity of J-weight [I]. Then dp[i-1][J-weight [I]] + value[I] (item I value), is the backpack put item I get the maximum value

So a recursive formula: dp [I] [j] = Max (dp [j], [I – 1] dp [I – 1] [j – weight [I]] + value [I]);

Step 3: How to initialize the DP array

In terms of initialization, it has to be consistent with the dp array definition, otherwise it’s going to get messy when it comes to recursing the formula.

Firstly, it is triggered from the definition of DP [I][j]. If the backpack capacity j is 0, that is, DP [I][0]. No matter which items are selected, the total value of the backpack must be 0. As shown in figure:

Let’s look at the other cases.

State transition equation dp [I] [j] = Max (dp [j], [I – 1] dp [I – 1] [j – weight [I]] + value [I]); You can see that I is derived from I minus one, so I must be initialized when I is zero.

Dp [0][j], that is, I is 0, the maximum value that can be stored by knapsack of each capacity when storing articles numbered 0.

The code is as follows:

// flashback throughfor(int j = bagWeight; j >= weight[0]; j--) { dp[0][j] = dp[0][j - weight[0]] + value[0]; // initialize I to 0}Copy the code

You should notice that this initializes to what is a flashback traversal? Can’t a positive order traversal work?

Dp [0][j] represents the maximum value of item 0 stored in a backpack with capacity J, and the value of item 0 is 15, because the title says ** each item has only one! ** so dp[0][j] should always be the value of item 0, i.e. 15, if not the initial value.

But if the sequence is traversed, item 0 will be added multiple times! For example:

// order traversalfor (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}
Copy the code

For example, if dp[0][1] is 15, then DP [0][2] = DP [0][2-1] + 15; Dp [0][2] = 30, then item 0 is added repeatedly.

So be sure to go backwards and make sure item 0 is put in only once! This is very important for the 01 backpack, later in the explanation of the scrolling array, will also use a flashback through to ensure that items are used once!

The initialization of dp array is shown in the figure below:

Dp [0][j] and dp[I][0] are already initialized, so how much should the other subscripts be initialized?

Dp [I][j] must have the highest value in the derivation. If the values given by the question are all positive integers, then it is ok to initialize the non-zero subscripts to 0, because 0 is the smallest and does not affect the result of taking the highest value.

If they give us a negative value, then the non-zero subscript is going to be initialized to negative infinity. For example, if the value of an item is -2, but its position is still initialized to 0, then the maximum value will be 0 instead of -2, so it will be initialized to negative infinity.

So that the DP array gets the most value out of the recursive formula, rather than being overwritten by the initial value.

The final initialization code is as follows:

// initialize dp vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}
Copy the code

It took so much effort to explain how to initialize the DP array clearly. I believe many students usually initialize the DP array by feeling, but sometimes the feeling is not reliable.

Step 4, determine the traversal order

In the figure below, you can see that there are two traversal dimensions: item and backpack weight

So the question is, do you go through the items first or the backpack weight first?

In fact, both can!! But it’s better to walk through things first.

So I’ll give you the code for walking through the items first, and then walking through the weight of the backpack.

// The size of the weight array is the number of itemsfor(int i = 1; i < weight.size(); I++) {// iterate over itemsfor(int j = 0; j <= bagWeight; J++) {// traverses the backpack capacityif(j < weight[i]) dp[i][j] = dp[i - 1][j]; // this is to show the changes of the elements in the dp arrayelsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); }}Copy the code

First through the backpack, then through the items, is also possible! (Note the two-dimensional DP array I used here)

For example:

// The size of the weight array is the number of itemsfor(int j = 0; j <= bagWeight; J++) {// traverses the backpack capacityfor(int i = 1; i < weight.size(); I++) {// iterate over itemsif (j < weight[i]) dp[i][j] = dp[i - 1][j];
        elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); }}Copy the code

Why is that ok?

Understand the nature of recursion and the direction of recursion.

dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – weight[i]] + value[i]); It can be seen from the recursive formula that dp[I][j] is derived by dp[i-1][j] and DP [i-1][j-weight [I]].

Dp [i-1][j] and DP [i-1][J-weight [I]] are both in the upper left direction of DP [I][j], so the process of traversing items first and then traversing the backpack is shown in the following figure:

Let’s go through the backpack first, then through the items, as shown in the picture:

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

But the sequence of going through the items first and then the backpack makes more sense.

In the knapsack problem, the order of the two for loops is very particular, and it’s much harder to understand the order of the loop than it is to understand the derivation.

The fifth step is to derive the DP array by example

Take a look at the values of the corresponding DP array, as shown below:

The end result is DP [2][4].

I encourage you to go through it on paper at this point, and see if each of the values in the DP array looks like this.

Do dynamic programming of the topic, the best process is to give an example on paper to the corresponding DP array numerical derivation, and then begin to write code!

A lot of students do DP questions, meet various problems, and then change things according to feeling, no matter how wrong, or confused.

The main reason is that I did not deduce the evolution process of DP array by hand. If the derivation is clear, there will be a problem if the code is written. As long as I print out the DP array and compare the difference with my derivation, I will soon find the problem.

Complete test code

void test_2_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; Vector <vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0)); / / initializationfor(int j = bagWeight; j >= weight[0]; j--) { dp[0][j] = dp[0][j - weight[0]] + value[0]; } // The size of the weight array is the number of itemsfor(int i = 1; i < weight.size(); I++) {// iterate over itemsfor(int j = 0; j <= bagWeight; J++) {// traverses the backpack capacityif (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagWeight] << endl; } int main() { test_2_wei_bag_problem1(); }Copy the code

The above traversal process could also be written like this:

// walk through the processfor(int i = 1; i < weight.size(); I++) {// iterate over itemsfor(int j = 0; j <= bagWeight; J++) {// traverses the backpack capacityif(j - weight[i] >= 0) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); }}}Copy the code

Write the printed DP data like this:

The empty 0 is actually useless, version 1 will print out the entire dp array.