———–

Background every day someone asked backpack problem, this problem is not difficult ah, if we number dynamic planning series of more than a dozen articles you have seen, with the help of the framework, encountered backpack problem can be said to be handy. It’s just state + choice, nothing special.

Today, let’s talk about the backpack problem, to discuss the most commonly said 0-1 backpack problem. Description:

You are given a backpack that can carry weight W and N items, each of which has weight and value attributes. The ith item weighs wt[I] and has a value of val[I]. Now, what is the maximum value that you can hold in this pack?

For a simple example, enter the following:

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
Copy the code

Algorithm returns 6, select the first two items into the backpack, the total weight of 3 is less than W, can obtain the maximum value of 6.

That’s it, a typical dynamic programming problem. The item in this question cannot be divided, either put in a bag or not put in a bag, not cut in half. That’s where the term 0-1 backpack came from.

There is no clever way to solve this problem, but to exhaust all possibilities, according to our “dynamic programming in detail” routine, directly go through the process.

Moving gauge standard routine

It seems that I have to repeat the routine for every dynamic programming article, and the dynamic programming problems in historical articles have followed the following routine.

The first step is to identify two things, “state” and “choice.”

Let’s start with states. How can we describe a problem situation? Just give a few items and a backpack capacity limit, and you have a backpack problem. So there are two states, “backpack capacity” and “optional items.”

And choice, it’s easy to think about, for each object, what can you choose? The choice is “backpack” or “no backpack”.

With states and choices in mind, the dynamic programming problem is basically solved, just follow this framework:

forstate1 instate1All values of:forstate2 instate2All values of:for. Dp [state1] [state2] [...]. = Choose the best1, the choice of2...)
Copy the code

PS: This framework comes from a historical article on the LeetCode stock issue.

The second step is to define the DP array.

First of all, let’s look at the “states” we just found. There are two, which means we need a two-dimensional DP array.

Dp [I][w] is defined as follows: For the first I items, the current backpack capacity is W, in which case the maximum value that can be held is DP [I][w].

For example, if DP [3][5] = 6, it means that for a given series of items, if only the first three items are selected, when the backpack capacity is 5, the maximum value that can be held is 6.

PS: Why do you define it this way? It’s easy to switch states, or that’s the way it works. Just write it down. Take a look at our series of articles on dynamic programming.

According to this definition, the final answer we want is dp[N][W]. Base case is dp[0][..] = dp[..] [0] = 0, because 0 is the maximum value you can hold when you have no items or no space in your backpack.

Refine the framework above:

int dp[N+1][W+1]
dp[0] [...] =0dp[..] [0] = 0

for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(Put item I into the backpack, do not put item I into the backpack)return dp[N][W]
Copy the code

PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.

Step 3: Think about the logic of state transition in terms of “choice”.

To put it simply, how can “put item I into backpack” and “don’t put item I into backpack” in the above pseudo-code be represented by code?

This will be combined with the definition of dp array and our algorithm logic to analyze:

To restate our definition of dp arrays:

Dp [I][w] represents: for the first I items, the maximum value that can be held in this case is DP [I][w] when the current knapsack has a capacity of W.

If you don’t put the i-th item in the backpack, then obviously the maximum value dp[I][w] should be dp[i-1][w], inheriting the previous result.

If you put the i-th item in the backpack, dp[I][w] should equal DP [i-1][W-wt [i-1]] + val[i-1].

First, since I starts at 1, val and WT are indexed i-1 to indicate the value and weight of the ith item.

Dp [i-1][W-WT [I-1]] is also easy to understand: if you are carrying the i-th item, you seek the maximum value of the remaining weight w-WT [I-1] plus the value of the i-th item val[i-1].

To sum up, there are two options. We have analyzed them all, that is to say, we have written the state transition equation, which can further refine the code:

for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(
            dp[i-1][w],
            dp[i-1][w - wt[i-1]] + val[i-1])return dp[N][W]
Copy the code

The last step is to translate the pseudo-code into code and handle some boundary cases.

[i-1] [w-wt] [i-1] [w-wt] [i-1] [w-wt] [i-1] [w-wt] [i-1] [w-wt] [i-1] [w-wt] [i-1] [w-wt] [i-1]

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    // Base case is initialized
    vector<vector<int>> dp(N + 1, vector<int>(W + 1.0));
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i- 1] < 0) {
                // In this case, you can only choose not to load the backpack
                dp[i][w] = dp[i - 1][w];
            } else {
                // Pack or not pack backpack, preferably
                dp[i][w] = max(dp[i - 1][w - wt[i- 1]] + val[i- 1], 
                               dp[i - 1][w]); }}}return dp[N][W];
}
Copy the code

So, the knapbag problem is solved, but I think this is a relatively simple dynamic programming problem, because state transitions come naturally, and basically you know what the DP array is, and you know what the state transitions are.

＿＿＿＿＿＿＿＿＿＿＿＿＿

My online e-book has 100 original articles, hand handle with brush 200 force buckle topic, suggest collection! The corresponding GitHub algorithm repository has been awarded 70K Star, welcome standard star!