3. Greedy Method - Introduction

hi next topic is greedy method this is one of the strategy for solving problems just like divide and conquer and the other strategies greedy method is also one of the approach for solving a problem or a design which you can adopt for solving similar problem the problems which fits into this one you can solve all of them let us understand what this method says what is this method about this method is used for solving optimization problem what are optimization problems

are problems which demands or which requires either minimum result or maximum result so for this let us know few terms I'll explain it through an example suppose there's a problem p and that problem is I want to travel from one location a to location B I have to cover this journey that is my problem for any problem I'm taking one example it can be any problem similar type now for this problem there may be more than one Solutions let us say I can travel this by walk Solution

One or I can take a bike solution two I can take a car solution three I can go by train solution four and I can go by flight solution five and there may be more solutions it can give me more solutions so my problem is to travel from location a to location B and there are many solution you go like this or take this take this and go there but there is a constraint in a problem I say that I have to cover this journey within 12 hours this is a condition constrain so suppose I cannot cover it

if I go by walk or by car and so I can cover it only if I go by train or flight now for a problem there are many solutions but these Solutions which are satisfying the condition given in the problem then these type of solution becomes feasible [Music] Solutions that's the meaning of feasible solution a solution which is satisfying the condition given in the problem is feasible solution though for a given problem there may be many solutions this is feasible solution

satisfying the constraint commonly we use the term Is it feasible or not feasible in the sense what satisfying our constraints or not limitations or not next if I say that I want to cover this journey in minimum cost minimum cost I want to spend as much as less possible then this becomes a minimization problem so now as the problem Demands a result should be minimum then it is a minimization problem right then out of these two solution one of the solution may be

taking minimum cost suppose by train if I go this is minimum cost then this is called as

optimal solution a solution which is already feasible and also giving me minimum cost that is best results that is best for me minimum is best for me then that solution is called as optimal solution and definitely for any problem there can be only one optimal solution there cannot be multiple Optimal Solutions that means there can be only one minim minum cost minimum can be only one there can be more than one Solutions there can be more than one feasible solution but there will be definitely

only one optimal solution this problem requires minimum result some other problems may require maximum result so if a problem requires either minimum or maximum results then we call that type of problem as

optimization problem optimization problem is one which requires either minimum result or maximum result so let us briefly look at the terms once again feasible solution means a solution which is satisfying some constraint optimal solution means which is achieving the objective of a problem satisfying the objective of a problem that is either minimum result or maximum result a problem which requires a minimum or maximum result is a optimization

problem so greedy method is used for solving optimization problems these are the strategies used for solving optimization problems [Music]

these three methods are for solving optimization problem the approach is different and every problem whichever requires optimal results some may be suitable here some may be suitable here this strategy can apply on it or some this strategy can be applied or some for some problems all three strategies can be applied on them so we will learn all these strategies through problems one by one now we are going to cover this greedy method so we will start with greedy method we will understand what

greedy method says what is the approach so next I will tell you about greedy method what is its approach here is the general method of greedy I have written an algorithm now see greedy method says that a problem should be solved in stages in each stage we will consider one input from a given problem and if that input is feasible then we will include it in the solution so by including all those feasible in inputs we will get a optimal solution so in stages we will each time we'll pick up

our input and we consider it and if it is feasible we will include it and like this if we follow this procedure we will get the optimal solution so here uh method is given if a problem is given and that problem is having a input of some size and N is the size and it is having some data some values input values now it will go through all those input values from 1 to n and each time it will select something from a and call it as X if that X is feasible that is one input one by one it

will pick up the input and that input if it is feasible it will include in the solution if it is feasible it is included in solution so this comes under if this is the general method now I will explain you through example the approach of gritty method is that suppose if you have to buy a best car best car best car in the sense in terms of features you want a best car optimal optimal okay the cost will be maximum definitely so but you optimal optimal in the sense for in terms of

features now how do you choose a best car how do you choose a best car so one method is you should look at all the brands and all the models of cars available in the world or at least in your city then you can say that I have checked all the cars then I have selected the best car this is one approach for solving a problem the problem is to buy a car this one method this will be very much time consuming you have to check each and every brand and every model see

the cost may not be a thing sometimes a car may be better than costlier car so checking with the features and you are deciding that this is the best car so but actually what is the method we follow we first of all sort out the brands and we say that we don't want in this this we want let us say you are selecting a brand that is Toyota or Hyundai right okay you are saying that these are the best brands for you and in these Brands then again you will select the top

models right so you are you are not looking at the lower models so again you have sort out then again you say that in this Top Model the latest release car or the well-known car well tested car you're picking up that one and you're saying that is the best one is it really the best one out of all the cars in the market for you it's the best one so what is the approach you adopted you have adopted a greedy approach so you have your own method of selection and based

on that selection method you got some result and you are seeing that is the best result that's how it is greedy and definitely when you do this you will be pick up a best car so you don't have to waste time in checking all the cars in the available in the city available in the market so that's it so without checking all of them you say that you select few and say this is the best car no doubt that's the best car but the approach you adopted is greedy I'll give you one more example

suppose you are running a company and you want to hire some people so when you have given an ad some thousand people came to for the interview now you'll conduct some type of test like you first you conduct return return test and then you have a technical test or group discussion like that you will have various phases of test and you'll filter the people and finally you select one person and you say that this is the best person on out of those thousand is he really a best person yes according to

your procedures it's a best person what was your selection procedure based on the selection procedure he is the best person and yes you have got the optimal solution so the approach is greedy many student complain that I was better than him and he got selected they think like that but really the person who got selected is the best one definitely so the approach that you're are adopting now I'll tell you if you selecting one person out of thousand then for all you

should give a chance for return return test for all you should give a chance for group discussion for all you should you should give a chance for technical interview and HR interview then pick up the best one this will be very timec consuming and costly process we don't do that we simply filter the people and select the best one this approach is called as greedy approach so we have our own methods of selection and we follow blindly we follow those methods because

those are the known methods when you follow known methods of solving a problem and you quickly solve it that approach is called as grey so I have given you enough idea about the greedy method now you will come across through the problems one by one I will pick up and I will solve them so in while discussing the problem also I'll show you what the approach GD is following so that if you type find any similar type of problem you can follow the same approach and solve

it that's it the introduction for gy method