Grokking Algorithms

Knapsack problem FAQ
Maybe this still feels like magic. This section answers some common 
questions. 
What happens if you add an item?
Suppose you realize there’s a fourth item you can steal that you didn’t 
notice before! You can also steal an iPhone.
Do you have to recalculate everything to account for this new item? 
Nope. Remember, dynamic programming keeps progressively 
building on your estimate. So far, these are the max values.
That means for a 4 lb knapsack, you can steal $3,500 worth of goods. 
You thought that was the final max value. But let’s add a row for
the iPhone.

---

172
Chapter 9
 
 
I
 
 
Dynamic programming
Turns out you have a new max value! Try to fill in this new row before 
reading on. 
Let’s start with the first cell. The iPhone fits into the 1 lb knapsack. 
The old max was $1,500, but the iPhone is worth $2,000. Let’s take the 
iPhone instead.
In the next cell, you can fit the iPhone 
and
the guitar.
For cell 3, you can’t do better than take the iPhone and the guitar again, 
so leave it as is.
For the last cell, things get interesting. The current max is $3,500. You 
can steal the iPhone instead, and you have 3 lb of space left over.

---

173
Knapsack problem FAQ
Those 3 lb are worth $2,000! $2,000 from the iPhone + $2,000 from the 
old subproblem: that’s $4,000. A new max!
Here’s the new final grid.
Question: Would the value of a column ever go 
down
? Is this possible?
Think of an answer before reading on. 
Answer: No. At every iteration, you’re storing the current max estimate. 
The estimate can never get worse than it was before!