3.1 Knapsack Problem - Greedy Method

hi a knapsack problem there's a van loan problem first of all we will know about the problem then we will see how it can be solved and then it'll also understand how grading method is applicable here and it is following reading method let us understand this problem see here some objects are given one two seven objects are given every object is having some profit associated with it and every object is having some weight so objects are there every object is having some profit and every object is having weight okay wait we understand what is this profit see there is a bag a given here that bag is called as knapsack the bag capacity is 15 these are seven objects bag capacity is 15 there is a path whose capacity is 15 let us say kg okay it can be cage is also pawn also it can be anything so I am assuming it as kg now what we have to do is we have to fill this bag with these objects and we will carry this back to a different place and we will celebrate these objects we get that profit so that profit is the gain that you get by transferring these objects to some location so for transferring you have to carry them in this container or bag so I can also call this knapsack as container this is a bag or knapsack I can also call it as container so the problem is a container loading problem so we find this type of problems in daily life lot of goods are transported daily from one place to another place now the problem is about filling of that container with the objects when it becomes a problem if you have the objects whose total weight is more than the capacity of the container back if you have less all can fit in than no problem at all if you have the objects more in number the way it is greater than the capacity for that then it is a problem so already we have some objects here so I have to fill this back these objects such that the profit is maximized profit is maximized so this is a optimization problem and it is a maximization problem maximization problem can we follow greedy method yes we can follow grading method an optimization problem if it is suitable next thing what is the constraint here the total objects included here in the bag the total weight should be less than or equal to 15 kg this is a constraint so I can give various solution I can say that just put only one object and take it it's not maximum I will say all on cannot fit in it's not feasible so it cannot be optimal so there can be many solutions you can say take this that and all and fill this one but we want maximum result that's it for a problem there can be many solutions but those solutions which are giving the solution which is giving maximum result is an optimal solution let us see how to solve this one see what I am going to do is for these objects I am going to include them so I will write down whether the object is going to be included or not included or how much it is included I will write down here X values so here I will be writing X 1 or X 2 or X 3 right X values I will be writing so this x value can be either 0 to 1 this X can be from 0 to 1 so it means I can also take fractions yes so now listen one thing very carefully this knapsack problem is for those objects which are divisible I have something of 5kg means I need not take all five kage I can just take 2 kg also 1 kg also so these objects can be divided so what type of objects if I take an example these may be vegetables 7 kg of potatoes fight edges of tomatoes something so instead of taking 5 kg I can take 2 kg also it can be divided yes so this is not about those objects which are indivisible let us say 5 kg grinder mixer 7 kg washing machine it cannot be divided it cannot take half of that washing machine so I have to take the full one so here I can take the fraction of an object also so that's how whatever I am including that can be a fraction starting from 0 to 1 now let us see how to include these objects in the back what should be my criteria method for including them in the bath you may be saying that this is giving highest profit take that one first yes that is giving highest profit take that one first but I can say that first fill the back with smaller things so that I can get more and more things in the bag and I can make more profit more things you carry more will be the profit so I prefer take this objects first with 1 1 kg weight or smaller weights so your idea is also good take the maximum profit 1 and my idea is also good take the smaller weights 1 so that I can have more objects but what is the right method I should select the objects which is having highest profit by weight is 18 is the profit so I say that 18 bucks is the profit then that profit is 4 for kg it's not for 1 kg for 4 kg so per kg how much so that's it we should select the objects who are having highest profit by weight but a kg whoever is highest that I should take so I should calculate one so I will calculate profit by weight for all these objects so this is 5 and this is 1.3 and this will be 3 this is 1 and this is 6 and 18 by 4 is 4.5 and this is 3 now I have these profits and weights of all those objects yes this is the right selection procedure for the object so the object should be selected based on their profit by weight so the one who is having higher highest profit by weight that I should fit put it in the back first all right now this is the greedy net heard let us see what the grading method is doing I was explaining it a problem so far then I said on what basis I should select this now he decided that we will select object based on their profit by weight this is our procedure now greedy method says that first you decide how you are going to select the input then go on selecting the input 1 megohm so we already selected the method we are going to select them by profit by weight now we will be going on including them one by one so which object I should include first in the bag the highest profit by me that is 5th object so I will include this whole thing so now this is this is 15 kg right so 15 - how many kg this profit this object is 1 so no remaining 14 kgs I have so I have included that sixth of fifth object in the back and I got the full profit - 6 now who is next this one I will select this one also this whole all 2 cases I will take so this is 14 minus 2 kgs now I have 12 kgs remaining in the back now which is the next object so I deserve the highest then this is the next highest this is the third is I will select this object also completely full so full runs all four cases I will include this is fate four cases have an include so this is - 1 - 4 is 8 kg 8 kg having right so 8 kg 8 kgs are remaining now this is the next one so I have three three these are two I can pick up any one so I will select this object so this is how many kgs now this is five cases don't look at the weight don't look at the weight I am selecting this one this is giving profit by weight so this is five kg and I will be getting 15 profit so the profit is same only for both of them it is same so I will select this so how many cases are gone 5 kg so 8 minus 5 I am left with just 3 kgs in the back now next is which one this one so I will take this whole thing so how many kg 1 kg so 3 kgs are there minus 1 now I'm left with 2 kg now that's the next one giving the profit so this one this one so I will include this but this is how many kg 3 kg how much I have there I have only 2 kgs remaining so can I include all these 3 cases there no I will be including only 2 kg there so this is 2 minus 2 0 it will become but from this one I am NOT taking the full object I am just taking 2 kg or 2 3 so this is 2 by 3 2 by 3 so I am taking the fraction of this object you said already I told you that these objects are divisible so I am taking 2 kgs out of that and what about this this is not included so I have a solution for this problem and this is the solution this shows how I am going to include objects which objects I should include so that I get the maximum profit now I have to calculate the profit and find out how much it is I have just written here the values from 0 to 1 now I will see total how much profit I get and I will also verify the weight that I am getting 15 kg only or not error right these values one with weight 1 into 2 plus 2 by 3 into this weight 3 plus 1 into 5 plus 0 into 7 plus 1 into 1 plus 1 into 4 kg plus 1 into 1 kg if I take this this is 2 plus this is 2 plus 5 plus 0 plus 1 plus 4 plus 1 so this is 9 10 14 plus 1 15 so yes the total weight is 15 only see these X so these are the X values this is either from 0 to 1 so that I am multiplying it abates so what is this sum of the X I in two-way time and that is less than equal to 15 so I have found out the total weight I was just subtracting now I'm just verifying it now let me know the profit so for profit also what I will do is 1 into 10 1 into 10 plus 2 by 3 into 5 2 by 3 into 5 plus 1 into 15 plus 0 into 7 I will avoid writing it then 1 into 6 1 into 6 plus 1 into 18 1 into 18 plus 1 into 3 1 into 3 this is the profit so there's nothing but summation of X I into P I every x value is multiplied with profit so this is showing how much quantity I am taking X now what is this totally equal to this is 10 plus is 2 into 1 point 3 plus 15 plus 6 plus 18 plus 3 so this is 54 point 6 so that's it our total profit is fifty four point six and that total weight is 15 once again I will show you something here see these objects are given then what is the constraint given in the problem the constraint is what some wealthy weights of the objects included in the back should be less than equal to capacity of the back yes we have done it see total weight should be less than equal to 15 and this is satisfied this is the constraint given in the problem so we have taken that solution which is satisfying the constraint yes the solution is satisfying so this is feasible and objective is what Objectivists sum of the weights profits of the objects that are included should be maximum this is the objective of a problem and we have achieved both now quickly I will explain you how we have followed the greedy method once again I am explaining you see the objects are given and the PAC is given we have to include these objects in the back such that the profit is maximum but the total weight should not exceed that one so we have to select some objects such that we guarantee that we are getting maximum profit so we have decided the criteria of selection have we tried this object No without trying how you can say that that is the best one because the method we followed is best one the method we followed is best one that we selected those objects whose profit by weight is higher and definitely whose whoever para kg values greater that will give you the maximum profit so that's all about knapsack problem there is one more problem called zero-one knapsack problem that is different from this one how it is different here fraction of an object is allowed but they indivisible objects fractions are not allowed so this is container loading with vegetables or fruits like this which are divisible things anything that is divisible and 0 on knapsack problem will be contained and loading but indivisible thing either you include that whole thing or it don't include at all so you cannot take part of it so that's all so I'll be making videos for all the topics that are there in greedy and then I will move on to dynamic programming and so on so I will be covering the entire syllabus what all the topics are there in the syllabus okay thank you for watching

Channel: Abdul Bari

Views: 2,009,028

Keywords: algorithms, algorithm, greedy method, knapsack problem, greedy knapsack, greedy knapsack problem, abdul bari, bari, gate

Id: oTTzNMHM05I

Length: 15min 30sec (930 seconds)

Published: Tue Feb 06 2018