For those interested in other dynamic programming problems, check it out

Dynamic programming at least coin change problem -JavaScript implementation

Detail dynamic programming longest common subsequence -JavaScript implementation

At the beginning, when you touch dynamic programming, you may be confused and seem to understand the idea, but you cannot accurately express or write the code. This paper will help students who are new to dynamic programming to understand the problem step by step through the way of drawing. This article will take the classic 01 knapbag problem as an example and end with a pure JavaScript implementation, running the demo on Sublime. Of course, it doesn’t matter if you don’t know JavaScript, because the most important thing is to understand the derivation. In the language implementation, there is no language features involved, basically understand a C language can understand.

The problem

Given a backpack of fixed size with capacity, there is a group of items with corresponding value and weight. It is required to find an optimal solution so that the total weight of the items in the backpack does not exceed capacity and the total value is the maximum. The value and weight of the goods are (3,2),(4,3) and (5,4). The value is on the left side of the bracket, the weight is on the right side, and the backpack capacity is 5. So find out its collocation combination, so that the total price of the backpack maximum, and the maximum value of what?

Analysis of the

Before computing, you need to have a basic understanding of the 01 knapsack problem in dynamic programming:

  • Items cannot be disassembled in the form of component numbers. If they can be disassembled, it is a greedy algorithm problem, and we will also introduce greedy algorithms in a later article.
  • It doesn’t have to be exactly full.
  • The total value is not necessarily maximum when filled.
  • One piece of everything
  • Normally, prices and weights increase from top to bottom in a table. When we fill out the analysis, we implicitly assume this ascending relationship.

Once you understand the above principles, you can begin your analysis. When a new item is introduced, a decision needs to be made as to whether it will maximize the total value if selected. According to the problems, we established the following table for analysis:

In the upper left corner, val and W are the value and weight of the item, respectively. That is, the value and weight of the three items described above.

From the third column to the last column, we use the variable j, which represents the total capacity of the backpack. The maximum value is 5, which is the value of capacity mentioned in the previous question.

The second row to the last row, denoted by I, starts at zero, and there are three items, so the maximum value of I is 2. That is, we use I for the item, and I =0 will be referred to as item 0, I =1 as item 1, and so on.

Except in the case of j = 0, we’re going to fill out this form from left to right, top to next step, to find the maximum value.

The blank space in the form indicates the total value of the items in the backpack. We will use the T[I][j] two-dimensional array to represent it later.

1. The total capacity is 0

If the total capacity of the backpack is 0, then obviously nothing can fit in the backpack, then the total value of the backpack must be 0. So the first step is to fill in the case where j is equal to 0.

2. Line 0, I = 0 space analysis

As mentioned above, we are going to fill out the form from top to bottom and left to right. So now focus on the space I =0, j = 1.

An important rule to follow during analysis is that row I can only be analyzed with combinations of items less than or equal to I.

How to understand this principle: For example, if you analyze the line I =0, then only item 0 can be placed in the backpack, and nothing else. Analyzing the line I =1, the combination of items can be item 0 and item 1

I =0 j=1: The total capacity of the backpack is 1, but the weight of item 0 is 2, so it cannot be carried, so this space should be filled with 0.

I =0 j=2: the total capacity of the backpack is 2, which is just enough to hold item 0. Since the value of item 0 is 3, fill this box with 3.

I =0 j=3: the total capacity of the backpack is 3. According to the item combination principle described above, only item 0 can be placed in line 0, without considering item 1 and item 2, so this box is filled with 3.

I =0 and j=4: Similarly, fill in 3.

I =0 j=5: Similarly, fill in 3.

In this way, we can complete line 0, as shown below:

3. Line 1, I = 1 space analysis

In this row, items 0 and 1 can be freely combined to load the backpack. I =1 j=1: The total capacity of the backpack is 1, but the weight of item 0 is 2, and the weight of item 1 is 3. The backpack cannot hold any items, so fill 0.

I =1 j=2: the total capacity of the backpack is 2, can only hold 0 items, so fill in 3.

I =1 j=3: the total capacity of the backpack is 3, at this time, it can hold an item 1, or an item 0. It is easy to understand that item 1 should be selected only from the way of filling in the form manually, but how should we express it with an exact logic and let the computer understand it? Based on the above said shows that the value and weight of the principle of increasing from top to bottom in the table, you can confirm that item 1 is greater than the value of items 0, so by default priority item 1, when selecting the items 1, knapsack capacity and remaining items before 1 items weight contrast (namely 0 and item weight contrast, if the rest of the weight can hold the previous article, So keep pretending. So pick item 1 here and fill in 4

I =1 j=4: After selecting item 1, the weight of item 1 is 3, and the backpack capacity is 4. After subtracting the weight of item 1, the remaining capacity is 1, which cannot hold item 0, so fill 4 here

I =1 and j=5 After item 1 is selected, the remaining capacity is 2, which is just enough to hold item 0. Therefore, item 1 and item 0 are packed in one compartment with a total value of 7. Fill 7 in the form.

This completes the second line, as shown below:

3. Line 2, I = 2 space analysis

I =2 j=1: fill in 0.

I =2 j=2: When filling in this line, all 3 items have a chance to be loaded into the backpack. If the total capacity is 2, you can only hold 0 items, so fill in 3.

I =2 j=3: the weight of item 2 is 4, which is larger than the capacity j, so it can refer to the value of T[i-1][j], namely, the value of I =1 j=3, fill in 4.

I =2 j=4: Can hold item 2, value 5. It can also hold item 1. Be careful with this space. We’re going to do it in a more rigorous way. In I =1 and j=5, items are grouped together in the backpack, which will continue this analysis. We have selected item 2, and the remaining capacity should be expressed as j-w[I], i.e. 4-4 = 0. The remaining capacity is used for the search of the previous line, which we have filled out, so we can easily obtain this value. The expression can be written as val[I] + T[I -1][j-w[I]], from which a value can be derived. However, this is not the final result, and it needs to be compared with the values of the same column in the previous row, namely T[i-1][j]. And then we put a 5 here.

I =2 j=5: According to the above calculation principle, if item 2 is selected here, then the maximum value can only be 5. Refer to the previous line, the same column, value is 7, take the maximum value. So discard item 2, select item 0 and item 1 in the backpack, and fill in 7.

The completed table is as follows:

Pseudocode representation

After understanding the whole process of filling the table above, we need to extract the logic and express it with pseudo code before implementing the specific code.

If (< j w [I]) {/ / capacity is less than the weight, can't hold T [j] = [I] T [I - 1) [j]; // So the value is equal to the previous row, same column. If I = 0, not on the line, then T [I] [j] take 0} else {T [I] [j] = Max (val [I] + T [I - 1] [j w. [I]], T [j] [I - 1]). I =2, j=4 and I =2, j=5}Copy the code

This short pseudocode is the core of the problem solving idea and can be applied to any programming language you are familiar with.

At this point, this article should basically come to an end.

JavaScript implementation

If you already understand the above form-filling analysis and pseudo-code representation, you can try to implement it in code yourself. In the end, a way to use JavaScript for your reference, no longer for the code to do too much, there will be comments in important areas. If Sublime supports pure JavaScript, you can copy paste directly and run Command + B to see the result.

function knapSack(w,val,capacity,n){ var T = [] for(let i = 0; i < n; i++){ T[i] = []; for(let j=0; j <= capacity; J ++){if(j === 0){T[I][j] = 0; continue; } the if (< j w [I]) {/ / capacity is less than the item weight, we can not hold the if (I = = = 0) {T [I] [j] = 0; / / I = 0, there is no I - 1, so T [I] [j] take 0} else {T [j] = [I] T [I - 1) [j]; // The capacity is less than the weight of the item, see previous line} continue; } if(i === 0){ T[i][j] = val[i]; / / row 0, there is no 1, I can only put this line that an item} else {T [I] [j] = math.h Max (val [I] + T [I - 1] [j w. [I]], T [j] [I - 1]). } } } findValue(w,val,capacity,n,T); return T; }! [](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/5/19/16377bff6e2d5c63~tplv-t2oaga2asx-image.image Function findValue(w,val,capacity,n,T){var I = n-1, j = capacity; while ( i > 0 && j > 0 ){ if(T[i][j] ! = T [j]) {[I - 1]. The console log (' select items' + I + ", weight: '[I] + + w' value: '+ values [I]); j = j- w[i]; i--; }else{ i--; }} if(I == 0){if(T[I][j]! = 0) {/ / then the first line items can also take the console. The log (' select items' + I + ", weight: '[I] + + w' value: '+ values [I]); }}} / / w = [r]. 2 and 4 val = (three, four, five), n = 3, capacity = 5 / / function knapSack ((2 and 4], [three, four, five], 5, 3); // var values = [3,4,5], weights = [2,3,4], capacity = 5, n = values.length; console.log(knapSack(weights,values,capacity,n));Copy the code

The output