Hello friends! And, welcome to GeeksforGeeks. This tutorial will make you go through the
Introductory concepts of Greedy Algorithms. Before we begin, lets consider a situation. There is this very intelligent guy who knows
programming. He is very rich and has an infinite supply
of 20$, 10$ and 5$ coins. Now he has a friend who needs some money. He ask for 35$ and that too in minimum number
of coins. Now if he was to just give money he could
have given it in quite a number of ways. He could give seven coins of 5$,a 10$ coin
and five 5$ coins and so on. But since he is supposed to pay minimum number
of coins, he has to come up with a greedy idea. After thinking for a while he proposes a solution. For every iteration, he has to give a coin
of largest value that does not take him past the amount to be given. Now for 35$ the largest denomination he can
start giving is 20$. Now 15$ are short to the amount,
so the next largest he can give is 10$. Now he need 5$ more and since he have it as
a denomination, one coin of 5$ and the loan is given in just 3 coins. Here the thing to note is that after every
iteration he is making a choice, one which is greedy in nature giving the coin
with largest value possible. This method will however not work for all
denomination and currencies. Now we will formulate the idea of greedy algorithms. Greedy Algorithm follows problem solving approach
of making the locally optimal choice at each stage
with the hope of finding a global optimum. So at each stage we select a locally optimal
value with the hope of getting to the best possible solution. This is a useful programming methodology. Lets see few of its Pros and Cons. So this approach is simple, easy to code and
implement, and have reasonable running complexity. However the main drawback for this method
is ,that there are very few cases wherein we end up getting the globally optimal value. With this example we'll see how the algorithm
makes locally optimal choices however ending up at a non optimal solution. So in this tree we are required to get the
largest root to leaf sum. That is starting from this root node here,
we have to find a path ending at a leaf node and having sum of nodes as maximum. So lets start from our root node. The sum at start is 3. There are two possible path, 4 and 7 however
here we make a greedy choice and choose the one that is maximum i.e 7. Our total now is 10. Now once at 7 we have to choose between 9
and 11. A greedy choice would be to select the larger
of the two. We select 11 and end up having a path with
sum as 21. Can we do better than this ?
Yes! we have a path. If we start from 3, go to 4 and then to 20,
this path would give us a sum of 27 which is greater than the one we have achieved through
greedy method. So here we conclude that making locally optimal
greedy choices don't always give us a globally optimal value. So, when are we suppose to use greedy methods
? All problems which are generally solved using
greedy algorithms satisfy two properties. The greedy-choice property, i.e making the
best choice at a moment leading to a global optimum. Next property is the optimal substructure,
problems whose optimal solution can be constructed efficiently from optimal solutions of its
subproblems This property may look similar to one in dynamic
programming however one thing to note here is that greedy algorithm never reconsider
its choices. This is the main difference from dynamic programming,
which is exhaustive and is guaranteed to find a solution. Finally we look at some applications which
uses greedy algorithms. Activity Selection Problem,
Huffman Coding, Job Sequencing Problem,
Fractional Knapsack Problem, Prim's Minimum Spanning Tree are few of such
applications. With this we wrap up this tutorial. If you have any doubts or suggestions please
leave them in the comment section below. Thanks for watching!