# Chapter 4: The Greedy Approach ## Overview Charles Dickens' classic character Ebenezer Scrooge may well be the most greedy person ever, fictional or real. Recall that Scrooge never considered the past or future. Each day his only drive was to greedily grab as much gold as he could. After the Ghost of Christmas Past reminded him of the past and the Ghost of Christmas Future warned him of the future, he changed his greedy ways. A greedy algorithm proceeds in the same way as Scrooge did. That is, it grabs data items in sequence, each time taking the one that is deemed "best" according to some criterion, without regard for the choices it has made before or will in the future. One should not get the impression that there is something wrong with greedy algorithms because of the negative connotations of Scrooge and the word "greedy". They often lead to very efficient and simple solutions. Like dynamic programming, greedy algorithms are often used to solve optimization problems. However, the greedy approach is more straightforward. In dynamic programming, a recursive property is used to divide an instance into smaller instances. In the *greedy approach*, there is no division into smaller instances. A ***greedy algorithm*** arrives at a solution by making a sequence of choices, each of which simply looks the best at the moment. That is, each choice is locally optimal. The hope is that a globally optimal solution will be obtained, but this is not always the case. For a given algorithm, we must determine whether the solution is always optimal. A simple example illustrates the greedy approach. Joe, the sales clerk, often encounters the problem of giving change for a purchase. Customers usually don't want to receive a lot of coins. For example, most customers would be aggravated if he gave them 87 pennies when the change was $0.87. Therefore, his goal is not only to give the correct change, but to do so with as few coins as possible. A solution to an instance of Joe's change problem is a set of coins that adds up to the amount he owes the customer, and an optimal solution is such a set of minimum size. A greedy approach to the problem could proceed as follows. Initially there are no coins in the change. Joe starts by looking for the largest coin (in value) he can find. That is, his criterion for deciding which coin is best (locally optimal) is the value of the coin. This is called the *selection procedure* in a greedy algorithm. Next he sees if adding this coin to the change would make the total value of the change exceed the amount owed. This is called the *feasibility check* in a greedy algorithm. If adding the coin would not make the change exceed the amount owed, he adds the coin to the change. Next he checks to see if the value of the change is now equal to the amount owed. This is the *solution check* in a greedy algorithm. If the values are not equal, Joe gets another coin using his selection procedure and repeats the process. He does this until the value of the change equals the amount owed or he runs out of coins. In the latter case, he is not able to return the exact amount owed. The following is a high-level algorithm for this procedure. ``` while ( there are more coins and the instance is not solved){ grab the largest remaining coin; // selection procedure If (adding the coin makes the change exceed the amount owed) // feasibility check reject the coin; else add the coin to the change; If (the total value of the change equals the amount owed) // solution check the instance is solved; } ``` In the feasibility check, when we determine that adding a coin would make the change exceed the amount owed, we learn that the set obtained by adding that coin cannot be completed to give a solution to the instance. Therefore, that set is unfeasible and is rejected. An example application of this algorithm appears in [Figure 4.1](#ch04fig01). Again, the algorithm is called "greedy" because the selection procedure simply consists of greedily grabbing the next-largest coin without considering the potential drawbacks such a choice. There is no opportunity to reconsider a choice. Once a coin is accepted, it is permanently included in the solution; once a coin is rejected, it is permanently excluded from the solution. This procedure is very simple, when a solution is possible, does the solution provided by the algorithm contain the minimum number of coins necessary to give the correct change? If the coins consist of U.S. coins (penny, nickel, dime, quarter, half dollar) and if there is at least one type of each coin available, the greedy algorithm alwys returns an optimal solution when a solution exists. This is proven in the exercises. There are cases other than those involving standard U.S. coins for which the greedy algorithm produces optimal solutions. Some of these also are investigated in the exercises. Notice here that if we include a 12-cent coin with the U.S. coins, the greedy algorithm does not always give an optimal solution. [Figure 4.2](#ch04fig02) illustrates this result. In that figure, the greedy solution contains five coins, whereas the optimal solution, which consists of a dime, nickel, and penny, contains only three coins. [](fig4-1_0.jpg) Figure 4.1: A greedy algorithm for giving change. [](fig4-2_0.jpg) Figure 4.2: The greedy algorithm is not optimal if a 12-cent coin is included. As this Change problem shows, a greedy algorithm does not gurantee an optimal solution. We must always determine whether this is the case for a particular greedy algorithm. [Sections 4.1](LiB0033.html#366), [4.2](LiB0034.html#399), [4.3](LiB0038.html#466), and [4.4](LiB0038.html#468) discuss problems for which the greedy approach always yields an optimal solution. [Section 4.5](LiB0038.html#470) investigates a problem in which it does not. In that section, we compare the greedy approach with dynamic programming to illuminate when each approach might be applicable. We close here with a general outline of the greedy approach. A greedy algorithm starts with an empty set and adds items to the set in sequence until the set represents a solution to an instance of a problem. Each iteration consists of the following components: - A ***selection procedure*** chooses the next item to add to the set. The selection is performed according to a greedy criterion that satisfies some locally optimal consideration at the time. - A ***feasibility check*** determines if the new set is feasible by checking whether it is possible to complete this set in such a way as to give a solution to the instance. - A ***solution check*** determines whether the new set constitutes a solution to the instance.