**Introduction To Greedy Algorithms**

A greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. This means that the choices made are only locally optimal, in the hope that the solution will be optimal globally.

We use greedy algorithms when we have an objective function that needs to be either minimized or maximized.

Unlike Backtracking, greedy algorithms have to come up with the most optimal choice in one shot. It cannot go back and change its decision.

Did you know, Greedy Algorithms were the asked in Google Kickstart 2020-a CodeJam Competition.

**Real-life example for Greedy Algorithms:**

Consider a boy named Ram. He has a box which can accommodate at most 3 chocolates. His friend offers him 4 chocolates namely A, B, C and D of Rs.10, Rs.20, Rs.30 and Rs.40 respectively. Ram can only choose as many chocolates as the box can accommodate. This means Ram can choose 3 chocolates at most.

Which 3 chocolates should he choose so that his profit is maximized??? Also, he can make only 3 choices. In each choice, he can pick one chocolate. Yes, you got it right… He should choose B, C, and D.

Let’s try to understand this situation algorithmically by applying the greedy approach. Initially, Ram’s box is empty and his friend has four chocolates.

**Step 1: **According to the definition of a greedy algorithm, Ram will choose the chocolate that will offer him the most immediate and largest profit. In this case, Ram will choose D because he will get a profit of Rs.40 which is greater than the profit made by choosing any other chocolate.

**Step 2:** Now Ram’s box has the capacity to accommodate 2 more chocolates. Ram has to choose 2 chocolates out of 3 such that “immediate” profit is maximised. He will choose C because of the same reason stated in step1.

**Step 3: **Now Ram’s box has the capacity to accommodate only 1 chocolate. Ram has to choose 1 chocolate out of 2 such that “immediate” profit is maximised. He will choose B because of the same reason stated in step1.

Now Ram’s box is full and profit is also maximised. You can try various combinations of choosing 3 chocolates out of the four chocolates in a given scenario and you will find that the profit is maximum for the above-mentioned combination with the least number of steps. So, In this case, our objective function was the profit that had to be maximised.

Some of the standard problems that can be solved using the greedy algorithm include the famous fractional knapsack problem, job sequencing problem, etc. Here, we will look at various graph greedy algorithms that are greedy algorithms and __Data Structure____.__