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
knapsack(), declare the variable
grid will be a two-dimensional list, or matrix, (a list of lists) where we store answers to our sub-problems.
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]
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).
After initializing our grid, we’ll want to populate it with values.
We can do this by iterating through each item in the
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
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.
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
The beauty of this solution is the index is also the weight capacity. For example, the
2nd column represents a knapsack of capacity
Even so, we’ll make things a bit more explicit.
Inside the loop, declare
weight_capacity and initialize it to