Solving Knapsack problem using Dynamic Programming

\[ \text {maximize}  16x_1 + 19x_2 + 23x_3 + 28x_4  \\
\text {subject to}  2x_1 + 3x_2 + 4x_3 + 5x_4 \le 7  \\
x_i \in \{0,1\}, \; i \in \{0…4\} \]

In bottom-up approach what we do is we compute the recursive equations bottom up. i.e. we start with zero items and find out what is the best we can do when we have 0 items to work with. And we take 1 item and find out what is the best we can do when we have 1 item to work with. We perform this up to j items which are 4 in our case. We create a big table with capacity along one side(row) and items on another side (column) and fill that table step by step. First, we take 0 items and try to optimize the Knapsack of size 0, then we take again 0 items and try to optimize for size 1. We perform this up to the total capacity of Knapsack which 7 in our case. We will have capacity +1 rows in the table. Similarly, we take 1 item and try to optimize the Knapsack of size 0 to capacity and so on up to a total number of items. This makes total no of times + 1 columns in the table. Now we have the table with size (capacity +1) along rows and (no of items + 1) along column. In our example, this is 8 x 5. This may look like this

First, we take 0 item. Since there is no item we cannot do any optimization. So the best optimization we get will be

Second, we take 1 item with weight = 2 and value = 16. Since the weight is 2 we need Knapsack with size at least 2. We cannot keep the item with Knapsack of size 0 and 1. So after taking one item, the table will look like.

Third, we take two items. The first item is one of given above and the next items are of size = 3 and value =  19. To keep this item we need Knapsack of size at least 3. Since total size of these two items is 5 the Knapsack of size at least 5 can hold both items. So the table for 2 items look like.

Similarly for 3 items.

and last for all 4 items

So the best optimization value is 44. Python Script for bottom-up dynamic programming is given below

bestvalues = [[0] * (capacity + 1) for i in range(1,2)]
    for i in range(1,itmes+1):
     for j in range(1,capacity+1):
      if weights[i-1] > j:
       bestvalues[i][j] = bestvalues[i-1][j]
      else:
       candidate1 = bestvalues[i-1][j]
       candidate2 = bestvalues[i-1][j-weights[i-1]] + values[i-1]
       bestvalues[i][j] = max(candidate1,candidate2)

This only gives the best values. But to determine which items are actually taken to make this optimized value we must backtrack the table. This can be done using following python script

reconstruction = []
    i = items
    j = capacity
    while i > 0:
        if bestvalues[i][j] != bestvalues[i - 1][j]:
            reconstruction.append(1)
            j -= weights[i-1]
        else:
         reconstruction.append(0)
        i -= 1