Greedy

A greedy solution is one where we can make every decision in the course of our algorithm based on some simple rule. To put it a bit more precisely, a greedy algorithm has the property that the locally optimal solution to any sub-problem will lead to a globally optimal solution.

Examples

• Making Change in fewest number of coins
  • Select the highest value coin with value no greater than the amount of change you have remaining to make (true with most real currencies, but not in general)
  • The locally optimal solution (choosing the coin with the highest value) will lead to the globally optimal solution (fewest coins)
• Task Scheduling to complete tasks by deadlines
  • If you are trying to figure out if you can get a bunch of tasks each with their individual deadline done on time, always work on the one with the earliest deadline first
  • The locally optimal solution (choosing the earliest deadline) will lead to the globally optimal solution (each task getting done (hopefully) before its deadline)
• knapsack with partial items
  • if you have a maximum weight to carry and want to maximize value (and can take fractions of an item), obviously you take items with highest value-to-weight first
  • The locally optimal solution (choosing your next item based on value/weight ratio) leads to the globally optimal solution (highest total value for a given weight)
• [Minimum Spanning Tree]

Recognizing Greedy Problems

Identifying greedy problems is something that is very easy to get wrong. Often new students will think a greedy solution is optimal, but will not have considered corner cases. This leads to coming up with more and more convoluted rules to apply as your greedy metric, and eventually it becomes very difficult to come up with a counter example. The answer will still end up being wrong, though.

In any case, there are several hints that a problem might be greedy

1. The algorithm involves decision making. You have to choose some item, or path. It should be noted that this only narrows the solution space to a few classes of algorithms, once you have a decision problem, you should see if you can come up with a greedy metric
2. You can prove a greedy solution is correct (see below)
3. There is some sort of diminishing returns. For instance if you can take multiple of an item, and each time, the value of the next of that item goes down, it's a strong hint that there is a greedy component to the solution.
4. Choices don't come with "strings attached". For instance, if you consider the scheduling problem above, and there was some strange rules about being forced to only work on some tasks before others, or only at certain times, it's a strong hint that it's NOT greedy. The big exception to this "hint" (not a hard and fast rule), is the bit about diminishing returns above.

So now the only thing that should be clear is that there is no sure way to recognize greedy problems. The best you can do is see if you can come up with a greedy solution and see if it works

Deciding if a Greedy Solution is Correct

So you think a problem MIGHT be a greedy problem, and you've come up with some greedy rule you think is right.

STOP!

you might be wrong.

The unfortunate about greedy is that it's one of the first techniques taught. Therefore students always