Knapsack01.md (1556B)
1 +++ 2 title = "Knapsack01" 3 +++ 4 5 # Knapsack01 6 7 ## Problem 8 9 Set of elements with a benefit and weight, and a total maximum weight. Have to find highest possible benefit. 10 11 W = 5 12 13 | S | B | W | 14 | --- | --- | --- | 15 | 1 | 2 | 1 | 16 | 2 | 5 | 2 | 17 | 3 | 4 | 3 | 18 19 20 ## Solution 21 Initialise a table: 22 23 | w (b) \ W | 0 | 1 | 2 | 3 | 4 | 5 | 24 | --- | --- | --- | --- | --- | --- | --- | 25 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 26 | 1 (2) | 0 | | | | | | 27 | 2 (5) | 0 | | | | | | 28 | 3 (4) | 0 | | | | | **RESULT** | 29 30 For each cell, in row with weight n: 31 value = max{ b(n) + b(one row up, n columns to left), value in cell above } 32 33 | w (b) \ W | 0 | 1 | 2 | 3 | 4 | 5 | 34 | --- | --- | --- | --- | --- | --- | --- | 35 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 36 | 1 (2) | 0 | <= 2 | <= 2 | <= 2 | <= 2 | <= 2 | 37 | 2 (5) | 0 | ^ 2 | <= 5 | <= 7 | <= 7 | <= 7 | 38 | 3 (4) | 0 | ^ 2 | ^ 5 | ^ 7 | ^ 7 | **<= 9** | 39 40 So the maximum benefit is 9. 41 42 To find the items that were taken, retrace: 43 44 - if the number comes from above, the item was not taken 45 - else, the item was taken. add the item, go up and move n columns to the left (where n is the weight of the taken item). repeat until 0. 46 47 Here, the items were 3 and 2. 48 49 [https://www.youtube.com/watch?v=8LusJS5-AGo](https://www.youtube.com/watch?v=8LusJS5-AGo) 50 51 ## Complexity 52 - for every k from 0 to n, consider Sk 53 - for every Sk consider w from 0 to W 54 - algorithm in O(nW) — size of matrix (pseudo-polynomial algorithm)