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!
Dostları ilə paylaş: