A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment, without worrying about the future result it would bring. In other words, the locally best choices aim at producing globally best results.

This algorithm may not be the best option for all the problems. It may produce wrong results in some cases.

This algorithm never goes back to reverse the decision made. This algorithm works in a top-down approach.

The main advantage of this algorithm is:

1. The algorithm is easier to describe.
2. This algorithm can perform better than other algorithms (but, not in all cases).

Feasible Solution

A feasible solution is the one that provides the optimal solution to the problem.

Greedy Algorithm

1. To begin with, the solution set (containing answers) is empty.
2. At each step, an item is added into the solution set.
3. If the solution set is feasible, the current item is kept.
4. Else, the item is rejected and never considered again.

Example – Greedy Approach

Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $28

Available coins:
  $5 coin
  $2 coin
  $1 coin

Solution:

1. Create an empty solution-set = { }.
2. coins = {5, 2, 1}
3. sum = 0
4. While sum ≠ 28, do the following.
5. Select a coin C from coins such that sum + C < 28.
6. If C + sum > 28, return no solution.
7. Else, sum = sum + C.
8. Add C to solution-set.

Up to the first 5 iterations, the solution set contains 5 $5 coins. After that, we get 1 $2 coin and finally, 1 $1 coin.

Greedy Algorithm Applications

• Selection Sort
• Knapsack Problem
• Minimum Spanning Tree
• Single-Source Shortest Path Problem
• Job Scheduling Problem
• Prim’s Minimal Spanning Tree Algorithm
• Kruskal’s Minimal Spanning Tree Algorithm
• Dijkstra’s Minimal Spanning Tree Algorithm
• Huffman Coding
• Ford-Fulkerson Algorithm