Greedy Algorithm

In this article, we will discuss what a Greedy algorithm is and how to implement it.

What exactly is the Greedy algorithm?

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global optimal solution are best fit for Greedy.

Greedy algorithms are mainly used for optimization problems.

What is an Optimization Problem?

Optimization Problem is maximizing or minimizing something. For example, Shortest Path Problem. In this problem we need to find a minimum distance path. Longest Path is also an Optimization Problem.

Let us consider one example problem to understand the Greedy Algorithm.

Let us suppose we have infinite supply of the following value coins: 10Rs, 5Rs, 2Rs, 1Rs. If someone asks for a fixed amount, how will you give this amount using a minimum number of coins? For eg. Amount= 15, Then You will pay in One 10Rs coin and One 5Rs coin.

Solution: In this problem, we will first consider all the coins in decreasing order. Then, we will take coins individually one by one. Then trying to pay the maximum amount by the current considered point, and whatever is the remaining amount, for that we go to the next Coin.

GENERAL STRUCTURE OF GREEDY ALGORITHM:

Getoptimal (Item arr[], int n)

1. Initialize: result =0
2. While( All items are not considered)

{ i=SelectAnItem()

if(feasible(i)) res=res+1;

}

3. Return Res

Important Note about greedy Algorithms: They may not work all the time.

To Justify this statement, let suppose in the above coin problem, if we have coins of values Rs18,1,10.

Coin[]={18,1,10}

Then according to Greedy Algorithm: Answer will be 3 Coins i.e. 18+1+1

But, Optimal solution would be 2 coins of Rs10 each.

Applications of Greedy Algorithms:

There are some standard problems which can be solved by Greedy Algorithm:

1. Activity Selection
2. Fractional Knapsack
3. Job Sequencing
4. Prim’s Algorithm
5. Kruskal’s Algorithm
6. Dijkstra’s Algorithm
7. Huffman Coding

There are lots of similar problems that use the greedy approach to find an optimum solution.