Tom Morgan, Jacob Steinhardt October 06, 2006
The greedy algorithm is perhaps the most straightforward and powerful algorithm you will learn. The idea is simple: given a problem in which you are trying to minimize or maximize something and have some system you can operate on, you ask what the best thing you can do if you were to only do one. Next, you updatethe system and repeat.
When it works
The greedy algorithm can be used when a local change (as in taking the current best action) will not detrimentally aﬀect the system as a whole. A classic example is as follows. Say you are low on funds and decide to rob a convenience store. To your misfortune you ﬁnd that the convenience store has been robbed by another criminal moments before hand. As thestore now lacks any cash, you decide to steal and resell some of the store’s donuts. The store has a variety of donuts which each can be sold for diﬀerent amounts. For example, they may have ten donuts that are worth $2 each, ﬁve that are worth $3 each and three that are worth $1 each. You have room for exactly seven donuts in your pack. What is the maximum amount of money you can make? The greedyapproach is to say: I have seven spots, what is the best donut I can pick for the ﬁrst spot? I take it and repeat. This amounts to taking as many of the most valuable ones as possible and then moving on to the next most. We quickly ﬁnd that the answer in this case is to take ﬁve $3 donuts and two $2 donuts.
When it doesn’t work
Taking the problem from before, it is no longer possible to solveif the donuts come in diﬀerent sizes and we can not take fractions of donuts. For example if we have six spaces, and there is a donut of size four that is worth $8 and there are two donuts of size three that are worth $5 each. The greedy solution says to ﬁrst take the $8 one but then we don’t have room for any more, while optimally we could ﬁt the two $5 donuts for a total value of $10.Heuristics
The way in which the current best is evaluated is called a heuristic. Given the previous example (in which greedy doesn’t work) possible heuristics include: the donut worth the most, the donut that takes the least space and (most logically) the donut with the highest ratio of value to size. What can make greedy problems diﬃcult is having complicated heuristics. When approaching a greedyproblem (or a problem you are trying to get partial credit on) do not be afraid to use multiple heuristics. By running multiple greedy algorithms and taking the best result, you can maximize your partial credit and on occasion simulate more complicated (and accurate) heuristics.
There are many techniques for proving or deriving Greedy algorithms, each requiring various levels ofmathematical sophistication. Usually, we can show that a Greedy algorithm work if all choices are independent of each other. Additionally, if the swap of two elements enacts only a local change (that is, all other elements remain unaﬀected, or the total value remains unaﬀected), then a Greedy algorithm will also work. Additionally, the Greedy can be derived by writing an inequality that willdetermine when the second element should come after the ﬁrst. Then, a sort should be performed using this criterion as the comparison method. This usually works (see below proof; it will work if a similar proof applies). Here is an example:
(US Open 2006) N cows go through a milking queue. The ﬁrst part of the process takes Ai seconds for cow i, and the second part takes Bi seconds for cow i.Only one farmer is available for each part of the process, so it is feasible that the second farmer will be doing nothing while the ﬁrst farmer is stuck milking a cow, or there can be a backup if the second farmer takes too long milking a cow (though the ﬁrst farmer can continue milking). Determine in O(N logN ) time the minimum time it takes to milk al lthe cows. First note that the total time...