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.