Learn
Technical Interview Problems: Dynamic Programming
Knapsack With Memoization: Filling in the Grid

With our grid built, we only need to fill it in to find our optimal value. Remember: each column is the capacity of a knapsack and each row is an item we can add. The first row is “no item” and the first column is “no capacity”.

We’ll consider the diamond first. It weighs 1 pound and is worth \$7. For each capacity after 0 (our first column), we can place the diamond in that location. Some capacities have spare weight, but that’s okay.

``````           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]``````

Let’s add a trophy worth \$6 and weighing 2 lbs.

The trophy doesn’t fit in a 1lb. knapsack, so we look at the previous row and fill this section with that value.

``````           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, (7), 7, 7, 7]
# third row: Trophy   [0, (7), ?, ?, ?]``````

The trophy fits in the 2lb. knapsack; we have two options:

1. Trophy plus value stored at the remaining weight
2. The previous best in the 2lb. sub-knapsack.

Adding the 2 lb. trophy would mean 0 remaining capacity. This is why “no capacity”, “no item” values live in our grid.

Option 1 = 6 (trophy value) + 0 (“no capacity” value)

Option 2 = 7 (the previous best)

By weighing our options, we see this section should store the diamond value even though there’s spare weight. We’re maximizing for value!

``````           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
# third row: Trophy   [0, 7, 7, ?, ?]``````

We repeat this process with the 3lb. sub-knapsack:

Option 1 = 6 (trophy value) + 7 (1lb. sub-knapsack value) Option 2 = 7 (the previous best)

``````           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
# third row: Trophy   [0, 7, 7, 13, ?]``````

One last time for the 4lb. knapsack:

Option 1 = 6 (trophy value) + 7 (2lb. sub-knapsack value) Option 2 = 7 (the previous best)

``````           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Diamond [0, 7, 7, 7, 7]
# third row: Trophy   [0, 7, 7, 13, 13]``````

Note that the best value is stored in our bottom-right section. This is true no matter how many items we add.

The order we consider items is irrelevant for the final value. Here’s how the grid would look trophy-first:

``````           # Capacity: 0| 1| 2| 3| 4|
#____________________________________
# first row: no item! [0, 0, 0, 0, 0]
# second row: Trophy  [0, 0, 6, 6, 6]
# third row: Diamond  [0, 7, 7, 13, 13]``````

### Instructions

1.

Let’s complete the logic for adding values to our grid. Inside the nested loops, we’re set up to evaluate each item for each sub-capacity.

Directly beneath the declaration for `weight_capacity`, add a conditional that checks if the `item`‘s weight is less than or equal to `weight_capacity`.

If it is less we want to weigh our options. Declare `item_value` and `item_weight` and initialize them to the appropriate values on `item`.

2.

We have two options:

1. Item plus value stored at the remaining weight
2. The previous best in the sub-knapsack capacity.

Declare `previous_best_less_item_weight` and set it to `grid[row - 1][weight_capacity - item_weight]`

`grid[row - 1]` retrieves the previous row, another list, and `[weight_capacity - item_weight]` retrieves the sub-knapsack capacity value.

Declare `capacity_value_with_item` and set it to the sum of `item_value` and `previous_best_less_item_weight`.

`capacity_value_with_item` represents option 1.

3.

Option 2 is the previous best at this sub-capacity. We can retrieve that with `grid[row - 1][col]`. Assign this value to `capacity_value_without_item`.

With both options in hand, we need to assign the appropriate value to `grid[row][col]`.

Set `grid[row][col]` to the `max()` of `capacity_value_with_item` and `capacity_value_without_item`.

4.

Now add an `else` to our `item.weight <= weight_capacity` conditional.

If the item doesn’t fit, we want to use the previous best. Set `grid[row][col]` to the value seen in the previous row.

5.

We’ve done it! All that’s left is to retrieve the final value.

Outside both of the nested loops, return the value in the bottom-right section of the grid.

You can access the row in the grid using `len(loot)` and the column using `weight_limit` or make use of Python’s `-1` index to retrieve the last values.