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ş: