Chapter 7
■
Greed Is Good? prove It!
141
... while owed >=d:
... owed -= d
... payed.append(d)
...
>>> sum(payed)
5632
>>> payed
[5000, 500, 100, 25, 5, 1, 1]
Most people probably have little doubt that this works; it seems like the obvious thing to do. And, indeed,
it works, but the solution is in some ways very brittle. Even changing the list of available
denominations in minor
ways will destroy it (see Exercise 7-1). Figuring out which currencies the greedy algorithm will work with isn’t
straightforward (although there is an algorithm for it), and the general problem itself is unsolved. In fact, it’s closely
related to the knapsack problem, which is discussed in the next section.
Let’s turn to a different kind of problem, related to the matching we worked with in Chapter 4.
The movie is
over (with many arguing that the TV show was clearly superior), and the group decides to go out for some tango,
and once again, they face a matching problem. Each pair of people has a certain compatibility, which they’ve
represented
as a number, and they want the sum of these over all the pairs to be as high as possible. Dance pairs of
the same gender are not uncommon in tango, so we needn’t restrict ourselves to the bipartite case—and what we
end up with is the
maximum-weight matching problem. In this case (or the bipartite case, for that matter), greed
won’t work in general. However, by some freak coincidence,
all the compatibility numbers happen to be
distinct
powers of two. Now, what happens?
2
Let’s first consider what a greedy algorithm would look like here and then see why it yields an optimal result.
We’ll be building a solution piece by piece—let the pieces be all the possible pairs and a partial solution be a set of
pairs. Such a partial solution is valid only if everyone participates in at most one of its pairs. The algorithm will then be
roughly as follows:
1. List potential pairs, sorted by decreasing compatibility.
2. Pick the first unused pair from the list.
3. Is anyone in the pair already occupied? If so, discard it; otherwise, use it.
4. Are there any more pairs on the list? If so, go to 2.
As you’ll see later, this is rather similar to Kruskal’s algorithm for minimum spanning trees (although
that works
regardless of the edge weights). It also is a rather prototypical greedy algorithm. Its correctness is another matter.
Using distinct powers of two is sort of cheating because it would make virtually
any greedy algorithm work; that is,
you’d get an optimal result as long as you could get a valid solution at all (see Exercise 7-3). Even though it’s cheating,
it illustrates the central idea here: making the greedy choice is
safe. Using the most compatible of the remaining
couples will
always be at least as good as any other choice.
3
In
the following sections, I’ll show you some well-known problems that can be solved using greedy algorithms.
For each algorithm, you’ll see how it works and why greed is correct. Near the end of the chapter, I’ll sum up some
general approaches to proving correctness that you can use for other problems.
2
The idea for this version of the problem comes from Michael Soltys (see references in Chapter 4).
3
To be on the safe side, just let me emphasize that this greedy solution would
not work in general, with an arbitrary set of weights.
The distinct powers of two are key here.