preface

The thief is not terrible, afraid of the thief culture, more afraid of the thief learned dynamic planning.

The body of the

Bai Yutang was a famous thief in all corners of the country, but the years do not forgive people, after the age of the legs and feet will not be quick, but a skill but no inheritance of the people. One day, a young boy came to learn art, hoping white jade soup can give advice on stealing. White Jade soup see the young bones qingqi, the heart has the idea of receiving it as a disciple, then out of the following question examination of the young:

Words landlord gold curator of the home has a special hidden treasure room, into the discovery after to steal things too much, but its load-bearing ability is limited, your package can only bearing 20 kg goods, and the value of each item is different, so the question comes, what items loaded backpack to regret it, to maximize total value? The relationship between weight and value is as follows:

Serial number Weight (W) Value (v)
1 2 3
2 3 4
3 4 5
4 5 8
5 9 10

The boy saw that it was a “01 backpack problem”, and then made the following analysis on the ground:

Let’s say the value of the items in our backpack is B. Add two parameters to the backpack: k and C, namely B (k, C). Then what does b(k,c) mean?

K represents the number of the item you are faced with, i.e. 1~5. C represents the remaining capacity of the backpack when you are faced with item K. B (k,c) represents the total value of the items in the backpack after you make a choice to take or not take item K

For example, b(2,20) represents the total value of the items in your backpack, given that your backpack is 20, when you are faced with item number 2 and make a choice to take or not take it.

With this concept in mind, let’s move on: Suppose you now encounter item number K, and your backpack is c, and you have to make a decision: Should you take item number K? So what’s the premise of taking it or not? Of course, is it heavy or not? Can I put it in my bag? So the first situation arises:

  1. If the weight of the KTH item w[k] is greater than the remaining weight C of the backpack, THEN I cannot carry it, i.ew[k]>c. So the value of the item in the bag now is the value of the bag after the previous item I picked up, i.eb(k,c)=b(k-1,c).I have the same amount of space left in the package, c.

In the second case, if I can carry the k item, that is, the weight of the k item w[k]< C, there are no more than two choices for the k item, take it or not, and THEN I have to make a decision based on the benefits generated after taking it away:

  1. If you don’t take item K, then the total value of the items in the bag at that timeb(k,c)=b(k-1,c)“, the same as the first one that couldn’t carry k.
  2. Take away item K, the total value of the items in the bag at that timeb(k,c)=b(k-1,c-w[k])+v[k]After I take the KTH item, the value in my bag must be the original value plus the value of the KTH item, and the remaining capacity in the bag after I take it isc-w[k]. To sum up, it is the following formula:b(k,c)=max{b(k-1,c),b(k-1,c-w[k])+v[k]}

The rest just needs to compare the smaller of these two ways which benefit more. The mind map is as follows:

After understanding the above description, coding is very simple, here I write in Java

class Main {
    public static void main(String[] args) {
        int[] w = { 0, 2, 3, 4, 5, 9 };
        int[] v = { 0, 3, 4, 5, 8, 10 };
        int N = 6, W = 21;
        int[][] b = new int[N][W];
        for (int k = 1; k < N; k++) {
            for (int c = 1; c < W; c++) {
                if (w[k] > c) {
                    b[k][c] = b[k - 1][c];
                } else{ int value1 = b[k - 1][c - w[k]] + v[k]; Int value2 = b[k-1][c]; B [k][c] = math.max (value1, value2); } } } System.out.println(b[5][20]); }}Copy the code

The results of 26

The last

In fact, before the public number has sent a similar “01 backpack problem” analysis – “using dynamic planning to solve the problem of childhood”, the majority of online blogs in the analysis of “01 backpack problem” are also using the form of drawing, similar to this:

recommended

  1. Recommend a conscience video, explain is also very detailed – 01 backpack problem
  2. Recommend an online view of the solution to the “01 backpack problem” website, a detailed description of the change processOnline 0/1 Knapsack problem solver

If you think this article is good, please feel free to like and retweet it. 😋 (flop,

Likes and retweets are the best support