Learn

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 `2`nd 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`.