Skip to Content
Learn
Technical Interview Problems: Dynamic Programming
Knapsack With Memoization: Building the Grid

Our brute force approach is inefficient! We’re compounding work by creating many different combinations that contain the same items. Just like with Fibonacci, we’re repeating computations that won’t change.

With the Fibonacci Sequence, we had one variable to store: the number itself. We could place that number in a Python dictionary and look it up as needed.

Now we’re dealing with multiple variables: the item’s weight and value as well as the capacity of the knapsack. A dictionary’s key-value pairs won’t be sufficient to store all the answers to our subproblems.

We’ll start tackling this problem by building a grid which can store all our sub-answers.

The columns of our grid represent each possible capacity up to the weight limit.

The rows of our grid represent each possible item we can fit into a knapsack.

Why do we want each possible capacity? Because finding the optimal capacity for a knapsack of weight 4 will be much more efficient if we already know the optimal capacities for knapsacks of weight 3 and 1!

Instructions

1.

Inside knapsack(), declare the variable grid.

grid will be a two-dimensional list, or matrix, (a list of lists) where we store answers to our sub-problems.

We create grid using two nested list comprehensions.

Here’s a pseudo-code representation:

# [ # [ 0 for capacity # in number of capacities + 1] # for item in number of loot items + 1]

Use range() for both list comprehensions. The inner list comprehension will place 0 for column in range(len(loot) + 1).

The outer list comprehension will do this for row in range(weight_capacity + 1).

2.

After initializing our grid, we’ll want to populate it with values.

We can do this by iterating through each item in the loot parameter.

We need information about the item as well as its location. Use enumerate(loot) for the iteration so we have access to row (the index) and item (the Loot instance).

Inside the loop, increment row by 1.

We do this because the first row is “no item” and we’ve already stored that sub-answer by using 0 as the default value.

3.

For each item, we want to consider how they fit into all of our sub-knapsacks.

Inside the first loop, make another loop that iterates for each column. You can use range(weight_limit + 1). Make the iterating variable col.

The beauty of this solution is the index is also the weight capacity. For example, the 2nd column represents a knapsack of capacity 2.

Even so, we’ll make things a bit more explicit.

Inside the loop, declare weight_capacity and initialize it to col.

Folder Icon

Sign up to start coding

Already have an account?