Source code online books for professionals by professionals

Figure 7-1.  A partial solution, and some greedily ordered pieces (considered from left to right), with the next greedy 
choice highlighted
1
No, it’s not to run away and buy comic books.

---

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.

---

Chapter 7 
■
 Greed Is Good? prove It! 
142