Grokking Algorithms

EXERCISES
8.1
You work for a furniture company, and you have to ship furniture 
all over the country. You need to pack your truck with boxes. All 
the boxes are of different sizes, and you’re trying to maximize the 
space you use in each truck. How would you pick boxes to maximize 
space? Come up with a greedy strategy. Will that give you the 
optimal solution? 
8.2
You’re going to Europe, and you have seven days to see everything 
you can. You assign a point value to each item (how much you want 

---

146
Chapter 8
 
 
I
 
 
Greedy algorithms
to see it) and estimate how long it takes. How can you maximize the 
point total (seeing all the things you really want to see) during your 
stay? Come up with a greedy strategy. Will that give you the optimal 
solution? 
Let’s look at one last example. This is an example where greedy 
algorithms are absolutely necessary.
The set-covering problem
Suppose you’re starting a radio show. You want to 
reach listeners in all 50 states. You have to decide what 
stations to play on to reach all those listeners. It costs 
money to be on each station, so you’re trying to minimize the 
number of stations you play on. You have a list of stations.
Each station covers a region, and
there’s overlap.
How do you figure out the smallest set of 
stations you can play on to cover all 50 
states? Sounds easy, doesn’t it? Turns out
it’s extremely hard. Here’s how to do it:
1. List every possible subset of stations. 
This is called the 
power set
. There are
2^
n
possible subsets.

---

147
The set-covering problem
2. From these, pick the set with the smallest number of stations that 
covers all 50 states. 
The problem is, it takes a long time to calculate every possible subset 
of stations. It takes O(2^
n
) time, because there are 2^
n
stations. It’s 
possible to do if you have a small set of 5 to 10 stations. But with all 
the examples here, think about what will happen if you have a lot of 
items. It takes much longer if you have more stations. Suppose you can 
calculate 10 subsets per second.
There’s 
no algorithm that solves it fast enough!
What can you do?