174
Chapter 9
I
Dynamic programming
What happens if you change the order of the rows?
Does the answer change? Suppose you fill the rows in this order: stereo,
laptop, guitar. What does the grid look like? Fill out the grid for yourself
before moving on.
Here’s what the grid looks like.
The answer doesn’t change. The order of the rows doesn’t matter.
Can you fill in the grid column-wise instead
of row-wise?
Try it for yourself!
For this problem, it doesn’t make a difference. It
could make a difference for other problems.
What happens if you add a smaller item?
Suppose you can steal a necklace. It weighs 0.5 lb, and it’s worth $1,000.
So far, your grid assumes that all weights are integers. Now you decide
to steal the necklace. You have 3.5 lb left over. What’s the max value
you can fit in 3.5 lb? You don’t know! You
only calculated values for
1 lb, 2 lb, 3 lb, and 4 lb knapsacks. You need to know the value of a
3.5 lb knapsack.
Because of the necklace, you have to account for finer granularity, so the
grid has to change.
175
Knapsack problem FAQ
Can you steal fractions of an item?
Suppose you’re a thief in a grocery store. You can steal bags of lentils
and rice. If a whole bag doesn’t fit, you can
open it and take as much as
you can carry. So now it’s not all or nothing—you can take a fraction of
an item. How do you handle this using dynamic programming?
Answer: You can’t. With the dynamic-programming solution, you
either take the item or not. There’s no way for
it to figure out that you
should take half an item.
But this case is also easily solved using a greedy algorithm! First, take as
much as you can of the most valuable item. When that runs out, take as
much as you can
of the next most valuable item, and so on.
For example, suppose you have these items to choose from.
Quinoa is more expensive per pound than anything else. So, take all
the quinoa you can carry! If that fills your knapsack, that’s the best
you can do.
If the quinoa runs out and you still
have space in your knapsack,
take the next most valuable item, and so on.
Dostları ilə paylaş: 
