Hey there and welcome back!
In this video we are getting started with another algorithmic approach which is the greedy algorithm.
Now, before we get started and deal with real coding interview questions, these are the four things
that we will first discuss.
Okay.
So first we will try to understand what the greedy algorithm is.
Then we'll try to understand what it is used for.
And after that we'll discuss what problems are suited for greedy algorithms.
And finally we will compare the greedy approach with dynamic programming.
All right.
So let's get started.
First let's discuss what the greedy algorithm is.
Actually, now we know that an algorithm is a series of steps or instructions used to solve a problem.
Okay.
Now when it comes to the greedy algorithm, this is a type of algorithm or a way of solving problems,
which is build step by step where the solution is built step by step, and at each step the algorithm
makes the choice that gives the highest immediate benefit.
Okay, so the key word over here is immediate.
The algorithm obviously would have to make choices at each step.
And the way that it decides which choice to make is by checking which choice gives the highest immediate
benefit.
Now let's try to understand this a little bit better.
And for this let's take an example.
Let's say there are two cities A and B, and a person wants to travel from A to B, and there are these
three paths.
And for traveling this path you'll have to spend $5.
And then for traveling this part over here, you'll have to pay $100.
And in a similar manner these paths also have their respective costs.
For example, this path over here costs $10.
And for example, this path over here costs $2.
And the person wants to go from point A to point B in a way that minimizes the cost for traveling from
A to B.
Now, if we were to approach this with a greedy algorithm, like if you were to try to find the solution
for this using a greedy algorithm, we would make the choice at every step that gives us the highest
immediate benefit.
So the person initially is at point A, and the person has to choose which way to go, whether to go
this way, this way, or this way.
Now when you compare these three costs, you can see that the minimum cost is this over here, because
this is just five.
And therefore this choice gives the highest immediate benefit.
And therefore the greedy algorithm would go ahead and choose this path.
But then after you reach over here, you can see that to reach point B from here you have to pay $100,
which is significantly higher than these paths.
Okay.
So this means that probably this question over here is not a good problem for the greedy approach.
But again, we're just trying to understand what it means with making the choice at every step such
that it gives the highest immediate benefit.
Okay, so that's what this would do over here.
The greedy algorithm would just go ahead and choose this path.
And we see that it's not the optimal path for solving this question.
Now another important thing to note about the greedy algorithm is that it does not reconsider its choices.
Now what does this mean?
It means that once the algorithm makes this choice and reaches over here, it would never get back and
reconsider this choice and consider what the cost would be if it had made this choice, for example.
Okay, so it does not reconsider its choices.
And in one of the future videos, we'll see that this is one of the major differences between the greedy
algorithm and dynamic programming.
Now, to further solidify what we have discussed over here, let's take one more example.
Let's consider this problem where we have a sack over here or a bag, and this bag has a capacity of
two kilograms.
And we have these four bags over here, which each weighs one kilogram.
And this one is made up of gold.
This is made up of bronze.
This is one kilogram of diamonds and this is one kilogram of iron okay.
And let's say we are trying to maximize the value that can be added into the bag such that this constraint
is met.
That is, the maximum capacity that can be added to the bag is two kilogram.
Now, if we were to approach this with a greedy algorithm, we would make choices at every step such
that it gives the highest immediate benefit.
So when you take a look at this, because over here you have gold, diamond, iron and bronze and all
of these are just one kilogram.
So the best choice that would give me the highest immediate benefit would be to add one.
Kilogram of diamonds to this bag over here.
Okay, because one kilogram of diamonds has the highest value among these four items.
So this is the first choice that the greedy algorithm makes.
And at this point, we have added only items worth one kilogram to the bag.
And we can still add one more kilogram to the bag because the capacity is two kilograms.
And therefore I would again make the choice.
That is, I would choose among these three the item that would give me the highest immediate benefit,
and that would be by adding one kilogram of gold to this bag over here.
And by now we have exhausted the capacity.
And this is how we would fill the bag such that this constraint is met and the value in the bag is maximized.
You can notice that this problem over here is a good problem for the greedy algorithm or greedy approach.
Again, notice that this question is similar, but a little bit different from the zero one knapsack
problem, which we have previously discussed.
Okay, in the zero one knapsack problem, the difference was that we had different items, but their
weights were different.
Okay.
And that's why the zero one knapsack problem cannot be solved using a greedy approach.
And rather it requires dynamic programming for solving this question.
We have already discussed this in a previous video, but I have slightly modified this question, and
I've made every item over here to have the same weight.
So you have one kilogram over here, one kilogram over here, and one kilogram for these two as well.
And we have seen that.
How?
By making this tweak.
This problem became a good problem for the greedy approach.
Or we were able to maximize the value in the bag by just picking items that had the highest immediate
benefit at every step.
And that is what the greedy algorithm does.
So by this point, we have got a good understanding of what the greedy algorithm is.
Basically, it's an algorithm that builds the solution step by step, and at every step the algorithm
makes the choice that gives the highest immediate benefit.
Now, in other words, we can say that the greedy algorithm chooses the locally optimal choice at every
step, hoping to find the global optimum.
Now, with local optimum, all that we mean is the choice at that particular instance which gives the
highest immediate benefit.
And with global optimum, we mean that the final solution has the optimal answer, or we arrive at the
optimal solution to the problem by making these series of choices where at every choice, we were not
thinking about the whole problem or the global best solution, but at every choice we were just focusing
on the locally optimal choice or the choice that would provide the highest immediate benefit.
So this is what the greedy algorithm is all about.
So we have got a good understanding of what the greedy algorithm is.
In the next video let's discuss what the greedy algorithms are used for.