01 Knapsack problem and scrolling array optimization space

preface

Small M company’s annual meeting luck burst and won the prize, the boss said to give you a capacity W snakeskin bag, go to the prize pool happy fishing. All the goods in the prize pool are unique. As much as the bag can hold, count. Different prize sizes and prices are different, and each prize once oh. Small M thought this opportunity once in a blue moon, I zha pull can let the boss pull bleeding.

This scenario, if reduced to an algorithm, is a typical knapsack problem. Can be simplified as:

There are N items, each of which has a volume W and a value V. Existing backpack has a fixed capacity, how to make the backpack into the total value of the items? Before addressing this issue, let’s briefly review dp’sThe principle ofAs well assolution

The principle of dynamic programming

Dynamic Programming, or DP for short. If a problem has many overlapping subproblems, dynamic programming is often the most effective. Each state in dynamic programming is derived from the previous state. For greed, there is no state derivation, but the local optimal is directly selected, and the divide-and-conquer method will be repeated many times in the subproblem. DP has memory, and it will be recorded in the calculation process. Sub-problems that need to be used in new problems can be directly extracted, avoiding repeated calculation and saving time.

The principle of optimality is the basis of dynamic programming. The principle of optimality means that “the optimal decision sequence in the multi-stage decision process has the property that, regardless of the initial state and the initial decision, for a certain state caused by the previous decision, the decision sequence in the subsequent stages must constitute the optimal strategy”.

Dynamic programming

1. Determine the meaning of the DP array and its subscript

2. State transition equations are derived

3. Initialize the DP array

4. Determine the order of traversal

For the first two steps above:

Abstract the problem, determine a model -> find constraints -> judge whether to meet the optimality -> find the relationship between big problems and small problems

1. Determine the meaning of the DP array and its subscript

dp[i][j]Represents the maximum value of the total value of the backpack with the remaining capacity of J, which is arbitrarily taken from the items with subscript [0-i].

2. Derive the state transition equation

The recursive formula can be divided into two cases:

1. Dp [I][j] = dp[i-1][j] = dp[i-1][j]

2. When the I item weighs less than the size of the rest of the backpack and can be put in. There are two cases.

   1. Put:dp[i][j] = dp[i - 1][j - w[j]] + v[i]
   2. Don’t put:dp[i][j] = dp[i - 1][j]

Now, for putting and not putting, we’re going to pick the larger value of both. Let me put a log diagram here to help you understand. Notice the last line of log.

Don’t understand? Dp [I][j] means to take any item with subscript [0-i] and put it into the backpack with residual capacity j, the maximum value of the sum.

3. Initialize the DP array

When the remaining capacity of the backpack is 0, you can’t put anything in it. So dp[I][0] = 0

vector<vector<int>> dp(wSize + 1, vector<int>(bagW + 1.0));
Copy the code

Dp [I][j] = Max (dp[i-1][j], dp[i-1][j-weight [I] + v[I]), we can know that I is derived from i-1, so I must be initialized when I is 0. Also, go through backwards to make sure item 0 is put in only once.

for (int j = bagW; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}
Copy the code

4. Determine the order of traversal

You see that in the recursive formula for this problemdp[i][j]Is made up ofdp[i-1][j]anddp[i - 1][j - weight[i]]Derived. It’s obvious from filling in a table and drawing a picture,dp[i-1][j]anddp[i - 1][j - weight[i]]All indp[i][j]The upper left corner of the. So it’s ok to go through the backpack first or through the items first.

So in summary, here’s the code

vector<int> weight = {1.3.5};

vector<int> value = {15.20.30};

int bagW = 5;

size_t wSize = weight.size(a); vector<vector<int>> dp(wSize + 1, vector<int>(bagW + 1.0));

for (int j = bagW; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

for(int i = 1; i < wSize; i++) {
    for(int j = 0; j <= bagW; j++) {
        if (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]); }}}printf("max value = %d", dp[wSize - 1][bagW]);
Copy the code

Optimized to a one-dimensional array

Roll arrays: Let arrays roll, plain and simple. This is the idea of trading time for space. Scrolling arrays are basically used in DP and recursion, most of which update one bit of the array by combining the values in the array with other numbers, then swap the positions of values in the array, and update the next bit.

In the last step, we found that if we use a two-digit array, the recurrence formula is:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + v[i])

And we also know that in dynamic programming each state is derived from the previous state. So dp[i-1] can be put directly into DP [I]. So it can be changed to:

dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + v[i])

The state transition equation above records the maximum value after each operation, but the result required is only the maximum value of the last row. Once you get the downstream data from the previous row, the data from the previous row is useless. So optimize the space with a one-dimensional array DP [J].

1. Determine the meaning of the DP array and its subscript

In the 01 backpack problem, DP [J] stands for: backpack with capacity J, the value of the items carried is dp at most [J].

2. Derive the state transition equation

Dp [j] can be derived from DP [j-weight [I]], indicating the maximum value carried by a backpack of j-weight [I] capacity.

Dp [j-weight [I]] + value[I] : knapsack with capacity j, add item I, subtract weight[I], add value of corresponding I

Dp [j] = dp[j-weight [I] + value[I]

So the recursion formula is:

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. Initialize the DP array

Since the backpack has a capacity of 0, the maximum value of the items it carries must also be 0.

4. Determine the order of traversal

For example: item 0’s weight[0] = 1, value[0] = 15

Positive order traversal:

dp[1] = dp[1 - weight[0]] + value[0] => dp[1] = 15

dp[2] = dp[2 - weight[0]] + value[0] => dp[2] = 30

At this point, DP [2] is already 30, and item 0 has been put in twice, so it cannot be traversed in order.

Traversal in reverse order:

dp[2] = dp[2 - weight[0]] + value[0] => dp[2] = 15

dp[1] = dp[1 - weight[0]] + value[0] => dp[1] = 15

So you need to go back and forward, so that each state is not the same as the previous state, so that each item is fetched only once. Also, if the traversal knapsack capacity is placed in the outer layer, then only one item will be placed per DP [j], i.e. only one item will be placed in the knapsack. So the traversal that requires knapsack capacity is going to be in the inner layer.

size_t wSize = weight.size(a);for (int i = 0; i < wSize; i++) {
    // Traverses the backpack capacity
    for(int j = bagW; j >= weight[i]; j--) {

    }
}
Copy the code

To sum up, the complete code

vector<int> weight = {1.3.5};

vector<int> value = {15.20.30};

int bagW = 5;

size_t wSize = weight.size(a); vector<int>(bagW + 1.0);

for(int i = 0; i < wSize; i++) {
    // Traverses the backpack capacity
    for(int j = bagW; j >= weight[i]; j--) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }}printf("max value = %d", dp[bagW]);
Copy the code

Some other algorithm notes

thanks

Thank you very much for the idea of code Capriccio. Before the author brush leetcode DP and binary tree class questions, often see the masterly solution of the problem. When reviewing the backpack problem, this article is also deeply inspired by the big guy.

Other algorithms are solved in detail