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.

Folder Icon

Sign up to start coding

Already have an account?