Greedy Algorithm

March 21, 2019

Defining Greedy Algorithm

An algorithm is called greedy if it follows the problem-solving heuristic of making the locally optimal choice at each stage with the aim of finding a global optimum.

In most situations, a greedy strategy does not lead to the optimal solution. Hence, it is extremely important to reason about the correctness of the greedy strategy before using it to solve a problem.

Problem 1: Too much to do!

Let’s say you have to maximise the number of tasks that you complete in a 10-hour duration. You are given an array T = [2, 4, 1, 6] where T_i denotes the time required to complete the i^th task.

The answer to this question would be 3 as you would choose to do tasks T₂, T₀ and T₁ — which take 1, 2 and 4 hours respectively to complete, for a total of 7 hours. Although we can easily calculate the answer in this small case, let’s see what our strategy would be in if there were many more tasks.

The greedy strategy for this problem is fairly straightforward. We always want to do the task with minimum duration first.

At each moment when you are required to make a decision, the optimal strategy would be to choose one of the remaining tasks which takes the minimum time. Here, our locally optimal choice is choosing the task with minimum time and we reach the global optimum by repeatedly doing this.

The following code carries out the greedy approach.

type=c odeblock|id=min_greedy|autocreate=cpp
int n = 7, hours = 50;
int T[7] = {10, 100, 4, 16, 8, 17, 28};
int sum = 0, i = 0;
sort(T, T+n);
for (i = 0; i < n; i++) {
    if (sum + T[i] > hours) break; 
    sum = sum + T[i];
}
cout << "Maximum number of tasks that can be done in " << hours << " hours is: " << i << endl;

Understanding when to use Greedy Algorithm

For a greedy algorithm, the most tricky part is to understanding the correctness of the algorithm. Hence, in this tutorial, we’ll spend quite a bit of time talking about various example problems and discussing the correctness of greedy approaches to the problem.

Problem 2: Rod Cutting

You are given a rod of length N. It can be cut into any number of pieces K, where K is less than N i.e. (K ≤ N). Each piece of rod can then be sold, and the price you can get for a piece of size i is represented by P_i. You need to find the maximum price you can get for the rod by splitting it into many pieces.

int rod_length = 10;
int P[] = {0, 1, 5, 8, 9, 10, 17, 18, 16} // P[1] refers to price of piece of length 1

The following are some possible ideas for greedy approaches to this problem.

Approach 1: Cut pieces based on maximum price per unit length: That is, maximize the ratio of price of each piece / length of piece i.e. P[i] / i. If we follow this greedy strategy,

The first piece we get is length 6, since that has the highest P[i] / i = 17 / 6 = 2.84. (price = 17)
Now we only have a rod of length 4 remaining. Among lengths 1 to 4, the best piece we get is length 3, with a ratio of 2.67. (price = 8)
Now we only have a rod of length 1 remaining. So our only option is to have the last piece be length 1, which has a ratio of 1.00. (price = 1)

This gives us a total price of 17 + 8 + 1 = 26.

The last piece might show you why this is bad greedy strategy. The ratio of length 2 is 2.50, so it would have been better to have two pieces of length 2 as opposed to one of length 3 and one of length 1.

Approach 2: Another greedy approach would be to choose the length with the maximum price of the possible lengths of pieces. Using that approach too, we obtain a price of 26 by cutting the rod in pieces of lengths 7 and 3.

Answer: If we had cut the rod pieces to be of length 2, 2 and 6, then we would have achieved a total price of 27 which is the optimal solution for the given input.

Classifying a problem as greedy

This problem illustrates how although some greedy approach to a problem might look promising at a first glance, we really need to reason about its correctness to be sure that it works.

Often proving the correctness of greedy requires rigorous mathematical proofs (and we’ll see some soon). One good question that you can ask yourself is, “Can we get a globally optimal solution by not choosing locally optimum option at any stage?”, or “In what ways can the locally optimal choice be bad for the global solution?“. These questions might help you come up with a good counterexample to the greedy algorithm.

For example, in the above problem, the bad thing about the locally optimal choice was that you’ll be left with a rod length that’s too small to achieve a good price per unit length (if the price per unit length is bad for all i <= length).

Implementing Greedy Algorithm

The second hurdle is deciding the parameter on which to apply the greedy algorithm.

In the example of maximising the number of tasks, we wanted to finish the task with minimum duration first. So our parameter was task duration.

In the second problem, we tried the parameters price per unit length, and price of piece. Neither of these parameters led to the optimal solution for the rod cutting problem.

Now, let’s try a problem where the greedy parameter exists, but isn’t obvious at first glance.

Understanding the correctness of a greedy solution

The previous question lays down the structure for reasoning about the correctness of a greedy approach.

The correctness of a greedy approach goes hand-in-hand with the parameter you choose for the greedy strategy. You cannot classify a problem as greedy vs non-greedy without knowing the parameter you’ll be implementing it on. For example, in the above problem the greedy strategy is only correct if the parameter is earliest finish time. For the other two parameters, the greedy strategy is not correct.
Correctness of greedy solution is usually proved by the method of contradiction. In the above problem, we used method of contradiction to prove that the earliest event finish time works as the parameter for greedy strategy.
Incorrectness of greedy solution is usually demonstrated by counter examples. In the above problem, we used counter examples to show that greedy strategies based on the other two parameters don’t lead to globally optimal solutions.

Summary

A greedy algorithm makes the locally optimal choice at each step with the aim of finding a global optimum.
It is extremely important to reason about the correctness of the greedy strategy.
The correctness of a greedy approach goes hand-in-hand with the parameter you choose for the greedy strategy. You cannot classify a problem as greedy vs non-greedy without knowing the parameter you’ll be implementing it on.
Correctness of greedy solution is usually proved by the method of contradiction.
Incorrectness of greedy solution is usually demonstrated by counterexamples.

Problems for practice

Here are some very interesting problems which will require a clear understanding of the above concepts: