About

An algorithmic approach for solving a problem by selecting the best available option at that moment of time, without bothering about the future results.

The local best choices made would lead towards globally best results.

It works in a top-down approach.

Iteratively makes one greedy choice at a time, reducing each problem into a smaller one.

That’s why the algorithm never reconsiders an earlier decision even if the choice is wrong.

Usually have to choose at each step a local maximum/minimum, so usually, we sort the input or use a fit data structure like a min/max heap.

When?

• optimization problems with big inputs
• if an optimal solution to the problem can be found by choosing the best choice at each step without reconsidering the previous steps once chosen
• if the optimal overall solution to the problem corresponds to the optimal solution to its subproblems

Advantages

• easier to describe
• can perform better than DP (but, not in all cases)
• can reach the optimal solution
• builds the solution step by step (finds the solution in an incremental way)
• offers a single solution (unlike backtracking)

Disadvantages

• doesn't always produce the optimal solution