1. Introduction
We humans are greedy animals. If you are given a backpack with a certain capacity and some items of different sizes, the items that are put into the backpack will belong to you. When encountering such good things, you will definitely not miss it. Tightening is not necessarily the best way, just use your brain. Here I will teach you how to solve such problems to get more prizes.
2. Application scenarios
Finding a subset in an item vector satisfies the following conditions:
1) The sum of the volume of this subset cannot be greater than the specified threshold value
2) The sum of the value of this subset of items is the largest in all subsets in vector V that meet condition 1.
3. Analysis
There are many versions of the backpack problem. This article only studies the 0/1 version, that is, the situation where an object is either selected or abandoned, and an object cannot be further subdivided. The easiest way to do this is to find all subsets of this vector, just like finding the subset of the power set, but this traversal method may not be used by smart people. The TV stations that hold these events are also very smart. They not only require you to load items in, but also specify the operation time. In this way, when you slowly load them in and pour them out, the time may have come long ago, and in the end you may get nothing. This is not the result we hope. We need to use some strategies: for the first time, we can pick one of the items smaller than the backpack capacity, so that we can try our best to get time. We hope that each of the first ones will be the best, which can save a certain amount of time. Suppose there is such a set of items, their size and value are shown in the following table:
| Item number | size | value |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 3 | 4 |
| 3 | 4 | 3 |
| 4 | 5 | 6 |
| 5 | 6 | 8 |
Give us a backpack with a capacity of 12, let us put the above items, we can use the following method to solve the problem of finding the optimal combination
Create a two-circular array, the array includes n rows (n is the number of items) and capcity+1 column
First, we make choices for the first item, because the size of item 1 is 2, first add item 1 to the backpack. The size of item 1 is 2, then when cap>=2, it can accommodate item 1. At this time, the value of the items in the backpack is =1, and we get the following array
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Next, the subset of item 1 and item 2 is processed. The size of item 2 is 3. It can only be accommodated when cap=3. When cap=3, it is said that it can accommodate item 2. At this time, the value in the backpack is = 4, and the remaining space is 0. When cap=4, it can accommodate item 2, and the remaining space is 1, and it cannot accommodate item 1. When cap=5, it can accommodate item 1+item2, and the value at this time is 1+4 = 5, and get the second line
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 0 | 1 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
The following analyzes item three, item two, and subset of item one. The size of item three is 4. When cap=4, it can accommodate item3. However, the value in the backpack is 3, which is obviously smaller than the value of cap=4 in the previous line (3<4). Therefore, when cap=4, it cannot be put in item3, so the position 4 of the third line should be consistent with the position 4 of the second line. When cap=5, it can accommodate item3, and the remaining space is 1. Just like in the case of cap=4, copy the value of the same position in the previous line. When cap=6, 2 are left after placing item3. It can accommodate item1 and item4, the total value of both: 1+3=4<5, so copy the value of the same position in the previous line. When cap=7, it can accommodate item2+item3, the total value is 7, which is greater than >5, so the value of cap=8 is 7, and when cap=9, it can still accommodate item3+item2, value=7, and when cap=8, it can accommodate item1+item2+item3, and the total value is 8, which is greater than the value of the same position in the previous line. Therefore, when cap>=9, the total value is 8, and the third line:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 0 | 1 | 4 | 4 | 5 | 5 | 7 | 7 | 8 | 8 | 8 | 8 |
According to this logic, you can get the following two columns, and the last two-circle array is
0，0，1，1，1，1，1，1，1，1，1，1，1
0，0，1，4，4，5，5，5，5，5，5，5，5
0，0，1，4，4，5，5，7，7，8，8，8，8
0，0，1，4，4，6，6，7，10，10，11，11，13
0，0，1，4，4，6，8，8，10，12，12，14，14
After obtaining such an array, what we need to do is to generate the optimal subset of items based on this two-circular array, the method is
Starting from the len line, compare whether the value of the cap index position of the last row is greater than the value of the same position in the previous row. For example, first compare the value of the position 12 of the fifth row (14) and the value of the position 12 of the fourth row (13). Because 14!=13, item5 is placed in the optimal set, and the size of item5 is 6. Therefore, compare the value of the position of the fourth row cap-6=6 and the value of the previous row at the same position, because 6! = 5, so item4 can be placed in the optimal set. The position to be compared in the next step is cap = =6-5=1. The position 1 of the third row is the same as the position 1 of the second row, so item3 cannot be placed in the optimal set, and the values on the first position of the second row and the first row are the same, so item2 cannot be placed in. Finally, it is determined whether item1 should be in the optimal set. After item5+item4, the remaining space is 1 and cannot accommodate item1, so the optimal set is {item4,item5};
Based on the above analysis, we can obtain such a processing process
1) First create a two-circular array of nx(cap+1)
2) The first line starts with trying to select the first item
3) For subsequent rows, for each capacity of 1<=cap<=capacity, first copy the value at the same position in the previous row. If the sum of the values and (tempMax) at the previous row () position is greater than the copied value, replace the copied value with the sum of the values and (tempMax) at the previous row () position (tempMax)
4) After obtaining the complete array, we can determine the optimal set based on the array. First, start from the last last position and compare with the same position on the previous row. If the same, the items corresponding to the index of the row cannot be placed in the backpack, otherwise they will be placed in the backpack, and start comparing the values indexed by the previous row with the previous row in the remaining space of the current backpack. If not, the corresponding items can be placed, so that the comparison between the second row and the first row is completed. Then, according to the comparison of the remaining capacity of the current backpack and the size of the first item, we determine whether the item can be placed in the backpack.
4. Source program
http://xiazai./201606/yuanma/Knapsack().rar
5. Conclusion
The above article uses dynamic programming to deal with such backpack problems. In the above article, the brothers also mentioned the problem of time complexity using recursive algorithms. They believe that recursive algorithms are relatively inefficient. This question is understandable, but recursive algorithms also have their advantages. Many problems can be solved by recursive. What I am currently learning is to use this algorithm to solve some common problems. For other algorithms, such problems can also be better solved by greedy algorithms, genetic algorithms, etc., but this article will not discuss them for the time being. If you have time in the future, these algorithms will be implemented and their advantages and disadvantages will be compared in detail.