Greedy Algorithms

We have to follow greedy approach in these algorithms, we to be very keen to achieve our goal. So, we work towards our goal only whether it is for maximising or minimising anything. These are the category of the algorithm which has 2 parameters to deal with the problems, and those are:

1. Divide the problem in sub-problems.
2. Safe Move.

Sub-Problem

When we have a big problem, we have to divide it in smaller problems so that it is easy for us figure out the solution for that problem.

Safe Move

Here, safe move refers to a move which is the first move of the sub-problem and gives us the optimal solution consistently.

Example

Consider the problem of finding the largest possible number from the given set of digits.

Here by applying greedy algorithm we have to divide the problem into smaller problem by considering one digit at a time.

Then we have to make safe move, i.e. we have to select the largest possible digit and then remove it from the original list. Keep on repeating this and we will be having our largest number at the end.

For Example, we have a list of numbers i.e. [9,1,2,3,5,7,6,8,9], in order to solve it, we first select 9, and remove it from the list, then we again select 9 and again remove it from the list, then we again select 8 and remove it from the list and so on. At the end we will end up with the largest number and which is 998765321.