Algorithms For Dummies

 Challenging Difficult Problems

Here is the code to execute the dynamic programming procedure described. (You 

can find this code in the 

A4D; 16; Knapsack.ipynb

 file on the Dummies site as 

part of the downloadable code; see the Introduction for details.)

import numpy as np

values = np.array([3,4,3,5,8,10])

weights = np.array([2,3,4,4,5,9])

items = len(weights)

capacity = 20

memo = dict()

for size in range(0, capacity

+1, 1):

    memo[(-1, size)] = ([], 0)

for item in range(items):

    for size in range(0, capacity

+1, 1):

        # if the object doesn't fit in the knapsack

        if weights[item] > size:

            memo[item, size] = memo[item-1, size]

        else:

        # if the objcts fits, we check what can best fit

        # in the residual space

            previous_row, previous_row_value = memo[

                        item-1, size-weights[item]]

            if memo[item-1, size][1] > values[item

                            ] 

+ previous_row_value:

                memo[item, size] = memo[item-1, size]

            else:

                memo[item, size] = (previous_row 

+ [item

                    ], previous_row_value 

+ values[item])

The best solution is the cached result when the code tests inserting the last item 

with the full capacity (20 kg) knapsack:

best_set, score = memo[items-1, capacity]

print ('The best set %s weights %i and values %i'

       % (best_set, np.sum((weights[best_set])), score))

The best set [0, 3, 4, 5] weights 20 and values 26

---

CHAPTER 16