1 Backpack Problem

First, take a very easy to understand example, which is also the example in the graphic algorithm. There is a bag that can only hold 4kg. The items include stereo 3000 yuan – 4kg, guitar 1500 yuan – 1kg, computer 2000 yuan – 3kg. How do you pack your bag for the highest value? (Note: Regardless of the size of the item, don’t think the guitar is too big to fit.)

1.1 answer

Believe this example, look casually can know what to install, must be installed computer plus guitar. It’s worth 3,500 bucks, and it’s just 4kg.

1.2 Why?

Come on, it’s such a simple question. One glance will tell you why. Because the rest of the combinations, you can’t get any higher than this value, and even if you get any higher than this value, you can’t put it down. Good. So that’s the simplest brute force algorithm. In red, you’re overweight and you can’t put it down.

In other words, when the number of items is 3, there are 2^3 possibilities, and then you find the one that fits, the one that fits the backpack, and you take the combination that has the highest value. So what if it’s four goods, or five goods? It’s hard to see at a glance if there are two to the fourth, two to the fifth combinations, but the logic is right, but the magnitude of the two to the n is too complicated.

Enter dynamic programming

The last dynamic planning entry article has written, dynamic planning, is small, small things. So how do you simplify this type of problem? How do you find representative models?

2.1 Let’s think about it

The current backpack carrying capacity is 4kg, this backpack has been loaded with the highest value items in the current situation, the value of V1. So, in this case, there is a new item, the weight of this item is X kg, the value is V, then for this 4kg bag, what is the maximum value of the item?

  1. Let’s take a look at how to pack this 4kg bag due to the emergence of new items. There are too many cases, but if you want to load the items with the maximum value, then it must be in line with the following situation. We don’t have to worry about x greater than 4.
  2. If the new item is to be loaded, the remaining load capacity after loading is (4-x)kg. Assuming that the maximum load capacity of the item is V2, the maximum value of the item that can be loaded in this 4kg bag is V +v2
  3. If this new item is not loaded, the maximum value of the 4kg bag can still be V1.
  4. Therefore, the maximum value of the 4kg package is V1 or V + V2

2.2 Keep thinking

  1. So how many possibilities are there for 4 minus x? 1kg, 2kg, 3kg. Based on that, we already know that the maximum value of a 4kg bag is v1. The maximum value that can be carried by the simple case of 1kg 2kg 3kg can also be deduced in the above way.

3. Complicate the problem

There is a backpack with a deadweight of 10kg, with five items, A 2kg 6 yuan, B 2kg 3 yuan, C 6kg 5 yuan, D 5kg 4 yuan, E 4kg 6 yuan. Ask how to put items, the highest value?

So let me draw some tables based on that

  1. First of all, weOnly item A, then bags of 1-10kg, for the case of only ITEM A, are as follows: Explain the table composition, especially the leftmost column, which represents the orderNew possession, the top line is the backpack value of different carrying capacity, and the rest is the maximum value of the corresponding item under the current carrying capacity.
  2. Now there is item B (there are two items A and B to choose from). Think about the conclusion of the above derivation and fill in the form as follows

Combined with the conclusion derived before, let’s explain in the column of 2kg. The first 6 yuan is when there is only a item, then the maximum value that can be put into the backpack is 6 yuan. When there is item B to choose from, there are two situations: (1) put item B into the bag, the carrying weight of item B is 0, then add item B value is 3 yuan (2) Do not put item B original value is 6 yuan, take the maximum, namely 6 yuan.

  1. Then there is item C (there are three items a, B and C to choose from at this time), which is not explained here, but directly shown in the picture above

Select the value of any node to verify:

At 7kg, we have finished the selection from ABCD, and now we need to consider the situation of adding E. The new item E is 4kg. If e is added, the remaining space is 3kg. As can be seen from the figure, a 3kg bag can hold items of 6 yuan at most before e is absent. The value of e is 6 yuan, so it adds up to 12 yuan, which is greater than the previous maximum value of 10 yuan, so the corresponding left marker is 12 yuan

4 Code Implementation

// function knapsack(weights, values, W){var n = weights. Length -1 var f = [[]] for(var j = 0; j <= W; J ++){if(j < weights[0]){if(j < weights[0]){ F [0][j] = values[0]}} for(var j = 0; j <= W; j++){ for(var i = 1; i <= n; i++ ){ if(! F [I]) {/ / to create a new line of f [I] = []} the if (j < weights [I]) {/ / is equal to the optimal value of f [I] before [j] = f [j] [I - 1]} else {f [I] [j] = math.h Max (f [I - 1) [j], [j] [I f - 1 - weights [I]] + values. [I])}}} the console log (f) return f [n] [W]} var = a knapsack (,2,6,5,4 [2], [6,3,5,4,6], 10) console.log(a)Copy the code

The final print is as follows

(I hope I can keep it up.)

Reference:

  1. SiTuZhengMei article segmentfault.com/a/119000001…
  2. Chapter on algorithmic graphic dynamic programming