1
00:00:00,230 --> 00:00:02,300
Hey there and welcome back!

2
00:00:02,330 --> 00:00:10,100
In the previous video, we have discussed that a greedy algorithm is an algorithm that chooses the locally

3
00:00:10,100 --> 00:00:15,500
optimum choice at every step, hoping to find the global optimum.

4
00:00:15,500 --> 00:00:21,650
So notice that the algorithm is hoping to find the global optimum.

5
00:00:21,650 --> 00:00:25,730
And this is what greedy algorithms are used for.

6
00:00:25,730 --> 00:00:29,210
So this is the question that we are going to discuss in this video.

7
00:00:29,210 --> 00:00:33,680
So greedy algorithms are used for optimization problems.

8
00:00:33,680 --> 00:00:36,230
Now what are optimization problems.

9
00:00:36,230 --> 00:00:43,370
These are problems that ask us to identify the minimum of something or the maximum of something, etc..

10
00:00:43,370 --> 00:00:48,890
So greedy algorithms are used for solving optimization problems.

11
00:00:48,890 --> 00:00:54,380
Now when it comes to a problem there would be some constraints, okay.

12
00:00:54,590 --> 00:01:02,960
And a problem can have many feasible solutions, but only one optimal solution.

13
00:01:02,960 --> 00:01:05,960
Now what do we mean with feasible solutions?

14
00:01:05,960 --> 00:01:11,780
Feasible solutions are solutions that meet the constraints of the problem.

15
00:01:11,780 --> 00:01:12,200
Okay.

16
00:01:12,200 --> 00:01:18,290
For example, let's say there's a student who goes to school and his parents tell him that you have

17
00:01:18,290 --> 00:01:22,580
to spend less than $20 per day on your food, okay?

18
00:01:22,580 --> 00:01:29,120
And then he has to decide what to eat every day such that this constraint over here is met.

19
00:01:29,120 --> 00:01:36,950
Now, if he is able to identify a combination of food items that costs less than $20 and he is satisfied

20
00:01:36,950 --> 00:01:43,880
with eating that, then he has identified a feasible solution or a solution that meets the constraints.

21
00:01:43,880 --> 00:01:49,940
But at the same time, a problem can have only one optimal solution.

22
00:01:49,940 --> 00:01:56,810
Considering the same example of the student, probably he wants to minimize the money spent per day

23
00:01:56,810 --> 00:02:01,430
on food because he wants to save up some money and buy a toy.

24
00:02:01,430 --> 00:02:08,270
Let's say, and let's say he's identified there is a particular meal that just costs $5 and it's sufficient

25
00:02:08,270 --> 00:02:14,060
to fill his stomach, and it's the least amount of money that he would have to pay per meal.

26
00:02:14,060 --> 00:02:17,960
Okay, let's say that's the scenario in our hypothetical example.

27
00:02:17,960 --> 00:02:21,860
So in this case, though, there are many feasible solutions.

28
00:02:21,860 --> 00:02:28,760
There is only one optimal solution which is buying this particular meal which just costs $5.

29
00:02:28,760 --> 00:02:36,530
So what we discussed is that a problem can have many feasible solutions, but only one optimal solution.

30
00:02:36,530 --> 00:02:38,540
And again, why are we discussing this?

31
00:02:38,570 --> 00:02:44,210
We are discussing this because greedy algorithms are used to solve optimization problems.

32
00:02:44,210 --> 00:02:51,470
Another interesting thing to note about greedy algorithms is that even though they are used for solving

33
00:02:51,470 --> 00:02:57,680
optimization problems, they don't guarantee to provide an optimal solution.

34
00:02:57,680 --> 00:02:58,550
Always.

35
00:02:58,550 --> 00:03:04,220
Okay, so a greedy algorithm will not give an optimal solution always.

36
00:03:04,220 --> 00:03:10,130
For example, we had discussed the problem where you had to travel from point A to point B, and we

37
00:03:10,130 --> 00:03:15,680
have seen that choosing the choice that had the least cost when we had to make the first choice did

38
00:03:15,680 --> 00:03:18,890
not guarantee the globally optimum solution.

39
00:03:18,890 --> 00:03:21,410
So this is a previous example that we discussed.

40
00:03:21,410 --> 00:03:28,250
So even though greedy algorithms are used for optimization problems, they do not guarantee to give

41
00:03:28,250 --> 00:03:30,470
an optimal solution always.

42
00:03:30,470 --> 00:03:37,910
Or in other words, we can use greedy algorithms to solve certain types of problems.

43
00:03:37,910 --> 00:03:40,340
So that brings us to the next question.

44
00:03:40,340 --> 00:03:44,390
What problems are suitable for greedy algorithms?

45
00:03:44,390 --> 00:03:46,820
Let's discuss that in the next video.