4.5 0/1 Knapsack - Two Methods - Dynamic Programming

the problem is zero and knapsack problem in this video I will explain what is zero a knapsack problem and how it can be solved using dynamic programming we will understand its approach next I will show you a tabular method for solving this one then also I will show you a sets method for swallowing this one so there are two methods we will see both the methods first of all let us understand what the problem is here I have some four objects for each object there is some profit and there is some weight and there is a bag of capacity M that is 8 is given the objective is to fill this back with these objects so can we put them all see the capacity a is 8 but the total weights of all these object is 14 so all objects cannot be filled in the bag so I have to carry few of those some of those objects there is subset of those objects and I have to carry them and sell them at other place so once I said I get this profit so I have to fill the objects such that the total profit is maximized and I have to give the solution in the form of a set for each object like for example this is included and this is not included or not included like this I have to write down which one is included or not included so it means I can write down each X I either 0 or 1 means the values can be 0 or 1 but not fraction so it means that the object that I am going to carry are not divisible breakable so I cannot take the fraction of that object so this means these are some solid objects may be a mixer or microwave oven or a router it can be something like this so which I cannot take 1/2 of a mixer in the back so these are indivisible objects so either I should carry the whole object or don't carry it at all so I have to carry the object such that the sum of the profits should be maximized and some of their weights should be less than or equal to the capacity of the back oh let us know the approach of dynamic programming for solving this one now few important things about dynamic programming dynamic programming is useful for solving optimization problem yes this demands maximum results for its optimization problem second thing dynamic programming says that the problem should be solved in sequence of decisions so yes we can take the sequence of decisions for every object we can take shall I include or not include or not include or not so I can take decisions I can even start taking the decision of the last object also include or not include wrong so usually in this one we take the decision from last object towards first object so he can take sequence of decision next thing one more point that dynamic programming says that you should try all possible solutions and pick up the best one now how many possible solutions are there see when I am writing the solution in the form of zeros and ones then it can be 0 0 0 means no object is included or 1 1 1 1 means all objects are included or 0 0 0 1 means only fourth object is included or first object is included or first two objects are included like this there are many possible solutions and some of them may be feasible some may not be feasible like all objects I cannot include so anyway I should try all of them and to pick up the best one so total how many solutions will be there so like four zeros and ones form if I continue so I will be getting to power four solutions so I should try to pause for solution for n objects it will be 2 power n solutions so if I try out all then the time complexity will be 2 power n this is too much time consuming so dynamic programming shows a easy method for doing the same thing we will not we will be indirectly trying all 2 power n right but not directly so we will not spend that much time let us solve this problem using tabulation emulation method let us see how to fill this values and how to get the solution for this problem so for solving as the capacity of the bag is 8 so I have taken the column so starting from 0 to 8 so this means that though the capacity is 8 but will not consider that 8 at once so we'll add weight 1 by 1 so starting from 0 then let us assume weight is 1 bit is 2 and so on then the rows for objects so I have taken 5 0 1 2 3 4 so starting from 0 so it means one by one we will consider the objects so initially we will not consider any object means will not include any object in the back so for filling this we have a formula so I will show you formula after some time after filling some values so let us see first row as a 0 object no object is included then what will be the profit so in these boxes I will be writing the profit so there is no profit gain when no object is included and even when the capacity of the bag is 0 these are the this is the capacity these are the weights right and these are weights and the profits of the objects so these are the weights and that is then 0 weight is there then all these are 0 0 0 next now we'll start filling so for that I will consider first object running consider first object I'll take this level and I will ignore all other objects and similarly when I go to second row I will ignore the remaining and I will take the second object as well as the first object I will consider the first object also so it means whenever I am in a throw I will consider all the objects in the previous rows also so for the first row directly I can fill it let us see first row what is the weight of the first object 2 so it can be filled only when the bag capacity is a 2 so here so what will be the profit 1 so fill 1 here that this means this is same that the previous value usually me write previous value only if required then rest of the cells the capacity of the bag is increasing but how many objects I'm considering only one so I don't have anything more to fill in the bag so only that object I can fill in the educating profit as 1 1 1 only I'll fill the second row also right third row also in the same way then I will write on the foreign law let us go to second row I am going to consider second object so as I said when we consider second object I should also include the first object so first let us look at the second object see the weight of the second object is 3 it can be filled in the bag only if the capacity is a 3 so in this cell only it can be filled so what is the profit that I'll get to support the two here what about this site it will be same value same value as the previous form then beyond this what should come here so as I said that when you are taking second object you should also consider first object so if I fill the second object also in the back total weight required is how much 5 so this is 5 and total profit will be 3 so both the objects can be filled when the capacity is 5 and the total profit will be 3 so here both of them can be filled right both of them I am considering both of them so now I have only 2 objects and this is giving for both objects not filled so rest of the values will be 3 3 3 then what will be the value here so as this is true so this will also be 2 so I can take the previous value or this value whichever is maximum I can take the same thing now I will fill the third object also then for the fourth object I will show you the formula third object let me consider third object if you look at this the maximum weight is this one and as they are arranged in increasing order of the weight so this is weight is 4 so this object can be filled in the bag only the capacity of the bag is 4 so this will be included in the bag and the capacity is 4 so the total profit that will be getting is 5 so this is then before that whatever the previous row values are so two one and zero now beyond us let us see see when I am on the third object I should also consider first and the second object also so if I just check them this is four and if I take these two objects it will be total six wait wait is six so these two objects I can fill if the weight is six all right actually if I want to fill these two then these two I can fill when the weight is seven this - I can fill if the weight is 5 and what will be the profit at 3 this object itself is 5 right now I will consider these two six and the total weight will be 6 so at 6 it will be 6 only right and when I consider these 2 so total is 7 7 and the profit is also 7 so at 7 the profit is 7 can we include all three it will be 10 but the capacity of the bag is only 8 so I cannot or include all three then beyond this the value will be 7 only and before this one the value will be same as this 5 all right now I will show you the formula and it will fill fourth row with that formula the formula is like this if I call this table as V this table as V then V of I comma W eyes the row number W is the column number is maximum of V of I minus 1 that is from the previous row I should take same value means previous row graduate should take this is the meaning or maximum of this one or what V of I minus 1 comma wait - weight of an object WI plus profit of an object that you are considering now let us the follow the formula and fill all these first one for comma one I will fill for comma one so V of four comma one is maximum of V of 3 comma 1 like this is 4 so this will be 3 comma V of 3 comma rate is almost 1 minus weight of an object weight of an object is 5 1 minus 5 plus profit of that object is 6 6 now this becomes a 3 comma minus 4 there is no such location so that value becomes undefined so only this value will be defined V of 3 comma 1 will be defined so V of 3 comma 1 is 4 2 0 so I should take 0 only there is will not be any such index V of 3 comma minus 4 is 4 that I have to take 0 only so it means up to what I will be getting negative numbers up to 58 up to 58 so till here I should fill these values as it is only so that's what I was saying that this can be considered or this can be considered in 4th so right on its value and all previous values as it is so the same thing here because there will be getting negative so till just wait till 5th weight before that till before that I have friend as it is now this 58 hopefully I will show you for this value 4 comma 5 V of 4 comma 5 as maximum of V of 3 comma 5 comma V of 3 comma there it is how much 5 minus weight of the subject is how much 5 plus profit of this object is how much 6 6 let us see V of 3 comma 5 3 comma 5 is how much 5 comma V of 3 comma Phi minus 1 Phi minus v 0 V of 3 comma 0 3 comma 0 is 0 plus 6 so which is greater 6 is greater so fill this value at 6 so that means this object is included here now 4 comma 6 I will find out vo of 4 comma 6 as maximum of V of 3 comma 6 comma V of 3 comma where it is 6 right and the weight of the object is 5 plus profit of the object is 6 so how much this is V of 3 comma 6 is how much 3 comma 6 is 6 6 comma V of 3 comma 6 minus 1 6 minus 5 that is 1 3 comma 1 3 comma 1 is how much 0 0 plus 6 so the answer is both are same only so take 6 only next one 4 comma 7 V off 4 comma 7 maximum of V of 3 comma 7 comma V of 3 comma V it is such a 7 so weight of the object is 5 7 minus 5 plus profit is 6 so this is 3 comma 7 is how much 7 comma this is V of 3 comma 7 minus 5 is a 2 3 comma 2 so 3 comma 2 is how much 1 plus 6 so this is 1 plus 6 so this is 7 only both I am getting 7 or 7 so they are similarly take 7 V of 4 comma 8 4 comma 8 is maximum of V of T comma 8 comma V of 3 comma weight is 8 minus the weight of an object is 5 plus profit is 6 3 comma 8 how much 3 comma 8 is 7 comma V of 3 comma 8 minus 5 is 3 3 comma 3 how much to sew this two plus six so how much this is this is 7 and this is 8 so onset is 8 so this is how the table is filled so I have used the formula for few cells in the last row and this can also be filtered directly also without the formula let me show you how to fill this last row directly I am considering fourth object whose rate is 5 and the profit is 6 so in fifth column just write 6 its profit and what to write on the cells before that same value as the previous row this is what you do first then beyond this now the weight is 5 beyond this the capacity of the bag is increasing so I can include other objects also so let us check other objects what I can include in the sixth column this object is definitely because its profit is maximum right 5 + 2 7 @ 6 nothing will happen so take 6 only at 7 I can consider these two these two so this is 6 plus 1 7 7 then at 8 when the bag capacity age of each of the objects I can consider Phi plus 3 8 so 6 n 2 8 so this is 8 so whichever objects that you can consider you just add them and in that capacity if they are fitting in you write on the max total profit so there's a simple method for filling the cells instead of following this complex formula you can follow that method so I have shown you both solutions I have to write down X 1 X 2 X 3 X 4 values now these now for finding these answers actually I will be taking sequence of decision now see the decisions can be taken only if you have the data yes we have kept the data ready the formula was used for filling this data now I have to take the sequence of decision so how to solve so actually I have to know which objects should be included and which should not be included in the bag so let us come with the maximum that is eight in the last cell this aid is generated only in fourth row and in that previous row you don't find eight anywhere so it means we got this aid because of including fourth object only so include the fourth object but profit is eight fourth object is included because it is not as in previous four now what is the profit of the a fourth object eight - profit is six so this is two now remaining profit is true not check whether - is there in the third row now have to check for the third object fourth then third then second and then one so third object - is there yes it's the same value - is there in the previous row also yes it is there so it means it is not because of third objects so don't include third object now let us consider second object is it - they're here in the second row yes - is there here is it there in the first row also no so it means this regard because of inclusion of the second object so take this sense one so now remaining is 2 minus 2 so 0 now 0 was it there in the first object so I have to consider the first object yes 0 was there in the first object or was it there in the zero dollar yes it was there in the 0th all so this row also so it means don't include object so this is the solution so it means which objects are England in the back x2 and x4 two objects are included in the back so that is x2 is this one x4 is this one so total profit will be 8 so this is the maximum profit of 0 and knapsack problem next I will solve it using sets method same problem I will do solid using set my target now let us solve it using set method set method will try to find all possibilities and pick up the best solution so let us see how sets are generated we will prepare a set of ordered pair that is profit and date so we'll start with the set 0 set to 0 and this we say no profit no weight means nothing is included the back then we will consider the first object that is 1 comma 2 whose profit is 1 and the weight is 2 so consider the first object so prepare a 0 of 1 and include this first object in the back so it will be 1 comma 2 e so actually add 1 comma 2 this ordered pair so we get this one now prepare set 1 then most these two order pairs and prepare this one so this means that we have considered first object so to order pairs are showing that first object is not included first object is included now let us prepare next set by considering second object so that is 2 plus 3 so prepare mix said that is s1 1 so add a 2 3 to these ordered pairs 2 plus 3 so this is 2 comma 3 then 2 plus 3 is added so this will become 3 plus 3 comma 5 then this is 2nd set for the second object so when you consider second object total for order pains all these are merged so this is 1 2 + 2 3 and this is 3 5 this means that no object is included first object is included second object is included both objects are included 4 possibilities are there so all the order pairs we got then prepare as 2 of 1 by considering third object 5 comma 4 add 5 comma 4 2 all so this Phi plus 4 so this is 5 plus 4 s 5 comma 4 only so 5 plus 4 so this will become 6 + 6 so this is 6 comma 6 5 plus 4 so this is 7 comma 7 so 5 is added to this and 4 is added to this so this become 8 comma 9 8 comma 9 now merge all these and take order pairs so set 3 we get as 0 0 1 2 then 2 3 then 3 5 then 5 4 then 6 6 7 7 now here 8 common 9 profit is 8 and the weight is 9 so that is exceeding the capacity of the back don't include that one so we have discarded that right now this is set 3 and this one if you observe this is profit this is weight profit increase weight increase then from this profit increase weight also increase profit increased and the weight also increase but here profit increase weight is decreased from 5 to 4 this is not possible profit is increasing so the weight is also increasing but a weight is decreased how it is possible so that's why this order paid are wrong so we have to discard an even so we will discard the one with the lesser profit smaller profit so 1 2 3 4 5 6 now we have only 6 order pays because to wear invalid one was this was giving wrong values and this was exceeding the capacity of the back so cutting of this one we call it as a dominance rule so with the dominance rule the values order Paris which is correct now I will consider food objects 6 comma 5 I will include so I will prepare set 3 1 by considering 4th objects 6 comma 5 so first order pair is 6 comma 5 next ordered pair is 6 and 5 are added so this is 7 comma 7 then 6 and 5 are added so this is 8 comma 8 and then 6 and 5 when they are added it will become 11 comma 9 6 & 5 added so this becomes 2 well comma 11 + 6 5 when added to 7 & 7 so this becomes 13 comma 12 now I have to prepare set for this is the final set most these ordered pairs so 0 0 is taken from here 1 comma 2 and 2 comma 3 and 5 comma 4 6 comma 6 & 7 comma 7 they are coming as it is now in this one 6 comma 5 is there so 6 comma 5 should come before 7 comma 7 so 6 comma 5 now here again you see their profit is remaining same but the weight is reducing so this should be removed then 7 comma 7 is there then 8 comma 8 is there then remaining 11 comma 9 exceeding the capacity of the back 9 11 and 12 so all three order pairs are gone so these are the ordered pairs I have so if you observe the method is generating all possibilities so this is one easy method of finding all possibilities so the time taken by this one is almost 2 power n now what is the solution so we have already sets now we take the sequence of decisions to solve this one now what is the maximum order fail 8 comma 8 so 8 comma 8 now using that I will solve this one so the approach is similar like what we saw in the tabular method 8 comma 8 belongs to set four but 8 comma 8 check whether it belongs to set 3 in the set tree 8 comma 8 was not there so it doesn't belong to set 3 therefore fourth object is included because of that only we got 4 comma 4 now I should take an ordered pair 8 comma 8 from this I should subtract the profit and weight of the fourth object so this is profit is 6 and the weight is 5 so the ordered pair is how much 2 comma 3 so now I should consider 2 comma 3 so now this was the first one now second 1 2 comma 3 now I have to consider third object so check whether it belongs to s 3 2 comma 3 yes it belongs to s 3 and two comma three belongs to s to check whether it belongs to s 2 s 2 comma trees there here also it means this is not because of the third object so therefore third object is not included in the back then now next step is I will consider second object 2 comma 3 belongs to set 2 for second object 2 comma 3 now does it belong to set 1 but 2 comma 3 doesn't belong to set 1 so 2 comma 3 was belonging to set 2 and 2 comma 3 does not belong to set 1 so therefore this is because of the second object that is included now what is the profit and weight of the second object 2 comma 3 so when you subtract 2 comma 3 from this 1 2 minus 2 0 and 3 minus 3 is 0 so this gives 0 comma 0 now first object I will consider now the step is 4 so 0 comma 0 belongs to set 1 and also 0 comma 0 belongs to set a 0 therefore first object is also not included 0 comma 0 belongs to s 1 also as 0 also it means this is obtained not because of the first objects so first objects also not included then the solution is from bottom if you see 0 1 0 1 so the answer is 0 1 0 1 so these two objects are included see the profit is 8 so we got a same solution with the help of sets also so this is one more method that's all about zero-one knapsack problem leave a comment and let me know whether it was easy for you to understand so I have shown you both the steps for solving 0 and AB sub problem right in some places we find tabulation method and some places we find the sets method

Channel: Abdul Bari

Views: 1,155,636

Rating: 4.8652468 out of 5

Keywords: algorithms, algorithm, dynamic programming, 0/1 knap sack, 0/1 knapsack, 0/1 knapsack problem, tabulation method, abdul bari, bari, gate

Id: nLmhmB6NzcM

Length: 28min 24sec (1704 seconds)

Published: Tue Feb 20 2018