Grokking Algorithms

Chapter 8
 
 
I
 
 
Greedy algorithms
A lot of people tell me that this algorithm seems easy. It’s too obvious, 
so it must be wrong. But that’s the beauty of greedy algorithms: they’re 
easy! A greedy algorithm is simple: at each step, pick the optimal move. 
In this case, each time you pick a class, you pick the class that ends the 
soonest. In technical terms: 
at each step you pick the locally optimal 
solution
, and in the end you’re left with the globally optimal solution. 
Believe it or not, this simple algorithm finds the optimal solution to this 
scheduling problem!
Obviously, greedy algorithms don’t always work. But they’re simple to 
write! Let’s look at another example.
The knapsack problem
Suppose you’re a greedy thief. You’re in a store with a 
knapsack, and there are all these items you can steal.
But you can only take what you can fit in your knapsack. 
The knapsack can hold 35 pounds.
You’re trying to maximize the value of the items you put 
in your knapsack. What algorithm do you use?
Again, the greedy strategy is pretty simple:
1. Pick the most expensive thing that will fit in your 
knapsack.
2. Pick the next most expensive thing that will fit in 
your knapsack. And so on.
Except this time, it doesn’t work! For example, suppose there are three 
items you can steal.

---

145
The knapsack problem
Your knapsack can hold 35 pounds of items. The stereo system is 
the most expensive, so you steal that. Now you don’t have space for 
anything else.
You got $3,000 worth of goods. But wait! If you’d picked the laptop and 
the guitar instead, you could have had $3,500 worth of loot!
Clearly, the greedy strategy doesn’t give you the optimal solution here. 
But it gets you pretty close. In the next chapter, I’ll explain how to 
calculate the correct solution. But if you’re a thief in a shopping center, 
you don’t care about perfect. “Pretty good” is good enough. 
Here’s the takeaway from this second example: sometimes, perfect is the 
enemy of good. Sometimes all you need is an algorithm that solves the 
problem pretty well. And that’s where greedy algorithms shine, because 
they’re simple to write and usually get pretty close.