Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition

CHAPTER 7

Greed Is Good? Prove It!

It’s not a question of enough, pal.

— Gordon Gekko, Wall Street

So-called greedy algorithms are short-sighted, in that they make each choice in isolation, doing what looks good right here, right now. In many ways, eager or impatient might be better names for them because other algorithms also usually try to find an answer that is as good as possible; it’s just that the greedy ones take what they can get at this moment, not worrying about the future. Designing and implementing a greedy algorithm is usually easy, and when they work, they tend to be highly efficient. The main problem is showing that they do work—if, ...