Hey there and welcome back!
In the previous video, we have discussed that a greedy algorithm is an algorithm that chooses the locally
optimum choice at every step, hoping to find the global optimum.
So notice that the algorithm is hoping to find the global optimum.
And this is what greedy algorithms are used for.
So this is the question that we are going to discuss in this video.
So greedy algorithms are used for optimization problems.
Now what are optimization problems.
These are problems that ask us to identify the minimum of something or the maximum of something, etc..
So greedy algorithms are used for solving optimization problems.
Now when it comes to a problem there would be some constraints, okay.
And a problem can have many feasible solutions, but only one optimal solution.
Now what do we mean with feasible solutions?
Feasible solutions are solutions that meet the constraints of the problem.
Okay.
For example, let's say there's a student who goes to school and his parents tell him that you have
to spend less than $20 per day on your food, okay?
And then he has to decide what to eat every day such that this constraint over here is met.
Now, if he is able to identify a combination of food items that costs less than $20 and he is satisfied
with eating that, then he has identified a feasible solution or a solution that meets the constraints.
But at the same time, a problem can have only one optimal solution.
Considering the same example of the student, probably he wants to minimize the money spent per day
on food because he wants to save up some money and buy a toy.
Let's say, and let's say he's identified there is a particular meal that just costs $5 and it's sufficient
to fill his stomach, and it's the least amount of money that he would have to pay per meal.
Okay, let's say that's the scenario in our hypothetical example.
So in this case, though, there are many feasible solutions.
There is only one optimal solution which is buying this particular meal which just costs $5.
So what we discussed is that a problem can have many feasible solutions, but only one optimal solution.
And again, why are we discussing this?
We are discussing this because greedy algorithms are used to solve optimization problems.
Another interesting thing to note about greedy algorithms is that even though they are used for solving
optimization problems, they don't guarantee to provide an optimal solution.
Always.
Okay, so a greedy algorithm will not give an optimal solution always.
For example, we had discussed the problem where you had to travel from point A to point B, and we
have seen that choosing the choice that had the least cost when we had to make the first choice did
not guarantee the globally optimum solution.
So this is a previous example that we discussed.
So even though greedy algorithms are used for optimization problems, they do not guarantee to give
an optimal solution always.
Or in other words, we can use greedy algorithms to solve certain types of problems.
So that brings us to the next question.
What problems are suitable for greedy algorithms?
Let's discuss that in the next video.