Chapter 9
I
Dynamic programming
At this point, your grid should look like this.
Remember, you’re trying to maximize the value of the knapsack.
This row represents the current best guess for this max.
So right now,
according to this row, if you had a knapsack of capacity 4 lb, the max
value you could put in there would be $1,500.
You know that’s not the final solution. As we go through the algorithm,
you’ll refine your estimate.
The stereo row
Let’s do the next row. This one is for the stereo. Now that you’re on the
second row, you can steal the stereo or the guitar. At every row, you can
steal the item at that row or the items in the rows above it. So you can’t
choose to steal the laptop right now, but you can steal the stereo and/or
the guitar. Let’s start with the first cell, a knapsack of capacity 1 lb. The
current max value you can fit into a knapsack of 1 lb is $1,500.
167
The knapsack problem
Should you steal the stereo or not?
You have a knapsack of capacity 1 lb. Will the stereo fit in there? Nope,
it’s too heavy! Because you can’t fit the stereo, $1,500
remains
the max
guess for a 1 lb knapsack.
Same thing for the next two cells. These knapsacks have a capacity of
2 lb and 3 lb. The old max value for both was $1,500.
The stereo still doesn’t fit, so your guesses remain unchanged.
What if you have a knapsack of capacity 4 lb? Aha: the stereo finally fits!
The old max value was $1,500, but if you put the stereo in there instead,
the value is $3,000! Let’s take the stereo.
|
