Grokking Algorithms

Chapter 9
 
 
I
 
 
Dynamic programming
You just updated your estimate! If you have a 4 lb knapsack, you can 
fit at least $3,000 worth of goods in it. You can see from the grid that 
you’re incrementally updating your estimate.
The laptop row
Let’s do the same thing with the laptop! The laptop weighs 3 lb, so it 
won’t fit into a 1 lb or a 2 lb knapsack. The estimate for the first two cells 
stays at $1,500.
At 3 lb, the old estimate was $1,500. But you can choose the laptop 
instead, and that’s worth $2,000. So the new max estimate is $2,000!
At 4 lb, things get really interesting. This is an important part. The 
current estimate is $3,000. You can put the laptop in the knapsack, but 
it’s only worth $2,000.

---

169
The knapsack problem
Hmm, that’s not as good as the old estimate. But wait! The laptop 
weighs only 3 lb, so you have 1 lb free! You could put something in
this 1 lb.
What’s the maximum value you can fit into 1 lb of space? Well, you’ve 
been calculating it all along.
According to the last best estimate, you can fit the guitar into that 1 lb 
space, and that’s worth $1,500. So the real comparison is as follows.
You might have been wondering why you were calculating max values 
for smaller knapsacks. I hope now it makes sense! When you have
space left over, you can use the answers to those subproblems to figure 
out what will fit in that space. It’s better to take the laptop + the guitar 
for $3,500. 

---

170
Chapter 9
 
 
I
 
 
Dynamic programming
The final grid looks like this.
There’s the answer: the maximum value that will fit in the knapsack is 
$3,500, made up of a guitar and a laptop!
Maybe you think that I used a different formula to calculate the value 
of that last cell. That’s because I skipped some unnecessary complexity 
when filling in the values of the earlier cells. Each cell’s value gets 
calculated with the same formula. Here it is.
You can use this formula with every cell in this grid, and you should 
end up with the same grid I did. Remember how I talked about solving 
subproblems? You combined the solutions to two subproblems to solve 
the bigger problem.

---

171
Knapsack problem FAQ