Greedy Algorithm

What is Greedy Algorithm? When and How to apply Greedy Algorithm?

What is a ‘Greedy algorithm’?

A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.

How do you decide which choice is optimal?

Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized.

The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.

Greedy Vs DP

In greedy we never go back and reverse the decision, remember this.