232
8.8
You’re making a map of the USA, and
you need to color adjacent
states with different colors. You have to find the minimum
number of colors you need so that no
two adjacent states are the
same color. Is this an NP-complete problem?
Answer:
Yes.
CHAPTER 9
9.1
Suppose you can steal another item: an MP3 player. It weighs 1 lb
and is worth $1,000. Should you steal it?
Answer:
Yes. Then you could steal the MP3 player, the iPhone, and
the guitar, worth a total of $4,500.
9.2
Suppose you’re going camping. You have a knapsack that holds
6 lb, and you can take the following items. They each have a value,
and
the higher the value, the more important the item is:
• Water, 3 lb, 10
• Book, 1 lb, 3
• Food, 2 lb, 9
• Jacket, 2 lb, 5
• Camera, 1 lb, 6
What’s the optimal set of items to take on your camping trip?
Answer:
You should take water, food, and a camera.
9.3
Draw and fill in the grid to calculate
the longest common
substring between
blue
and
clues
.
Answer:
Dostları ilə paylaş: 
