Grokking Algorithms

Chapter 9
 
 
I
 
 
Dynamic programming
Every dynamic-programming algorithm starts with a grid. Here’s a grid 
for the knapsack problem.
The rows of the grid are the items, and the columns are knapsack 
weights from 1 lb to 4 lb. You need all of those columns because they 
will help you calculate the values of the sub-knapsacks.
The grid starts out empty. You’re going to fill in each cell of the grid. 
Once the grid is filled in, you’ll have your answer to this problem! 
Please follow along. Make your own grid, and we’ll fill it out together. 
The guitar row
I’ll show you the exact formula for calculating this grid later. Let’s do a 
walkthrough first. Start with the first row.
This is the 
guitar
row, which means you’re trying to fit the guitar into 
the knapsack. At each cell, there’s a simple decision: do you steal the 
guitar or not? Remember, you’re trying to find the set of items to steal 
that will give you the most value. 
The first cell has a knapsack of capacity 1 lb. The guitar is also 1 lb, 
which means it fits into the knapsack! So the value of this cell is $1,500, 
and it contains a guitar.

---

165
The knapsack problem
Let’s start filling in the grid. 
Like this, each cell in the grid will contain a list of all the items that fit 
into the knapsack at that point. 
Let’s look at the next cell. Here you have a knapsack of capacity 2 lb. 
Well, the guitar will definitely fit in there!
The same for the rest of the cells in this row. Remember, this is the first 
row, so you have 
only
the guitar to choose from. You’re pretending
 
that 
the other two items aren’t available to steal right now.
At this point, you’re probably confused. 
Why
are you doing this for 
knapsacks with a capacity of 1 lb, 2 lb, and so on, when the problem 
talks about a 4 lb knapsack? Remember how I told you that dynamic 
programming starts with a small problem and builds up to the big 
problem? You’re solving subproblems here that will help you to solve 
the big problem. Read on, and things will become clearer.

---

166