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:

- Trophy plus
**value stored at the remaining weight** - 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]
```

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`

.

We have two options:

- Item plus
**value stored at the remaining weight** - 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.

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`

.

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.

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.