0/1 Knapsack Problem Dynamic Programming



hello friends my name is too short and today I am going to talk about zero-one knapsack problem so I have an old video on this question but I felt that I missed few things in that videos I'm creating a new video to fill those gaps so what is 0-1 knapsack problem suppose I have a total weight and then I have certain items with their weights and values how do you pick items from this set such that the sum of their values is maximum but some of their weights is less than or equal to total weight also we have just one quantity of each item so what does 0 1 means 0 1 means that either you pick the item or you don't pick the item it means that you cannot split the item so if it was not a zero-one knapsack problems just say that you could have split the item there is a greedy solution to solve that question all you have to do is solve the item by the value 2 weight sort the item by value to weight in a non increasing order and then keep picking the items and then if the last item cannot be picked totally split it up and pick whatever ratio you can so but here we are you doing 0 a knapsack problem it means that we cannot split the item so how do we do it yes we will use dynamic programming to solve this question in the next section let's see how so how do we solve this problem so the question is very simple whenever a new item comes in you have to decide you have to pick this item or not and you have to find which gives you the maximum value if you pick the item the maximum value will be the value of the item plus whatever we can get by subtracting subtracting this value the this value from the total weight and excluding this item or the best you can do without including this item all together let's try to understand on with this example so here I have a 2-dimensional matrix and this is my total number of columns is same as a total weight plus 1 and my number of rows is same as the total items so our first column is 0 it means that if the total weight is 0 no matter what items I have my maximum value I can get is always zero so this is why this all is zero so let's start from here so if my total weight was one and if I just had one item one the best I can do is one so this is the weight of the item the total weight is one so the maximum value I can get is just one if my total weight is 2 if I just had one item of weight 1 and whose value is 1 the best I can do is 1 remember we just have one quantity of each items so even though the total weight is 2 if I just have item 1 I get the Mac best I can do is value 1 similarly 1 1 1 1 1 so if the total weight is 7 with the only animal I have is weight 1 and whose value is 1 the best I can do is 1 because we have one quantity of each item so next let's introduce 3 since the total weight is 1 and if the weight of the item is 3 which is greater than the 1 so 3 can never be in there can never be selected so what we do is what is the best we can do without selecting 3 so basically this number so that's 1 again 2 since 2 is less than 3 3 can never be selected since the total weight is less than 3 so the best we can do is without 3 what is the best we can do which is this number so that's 1 now 3 so since 3 is since 3 is less than equal to 3 we have 2 choices do we select 3 or we do will not select 3 if we select this item the so we have to check what is the best you can do by selecting this item if we did select this item this gives me a value 4 plus whatever width is remaining after we select this weight so 3 minus 3 so that's 0 so T of 0 and then and then we go to the top column so that also 0 so we reach this point so we go up we go three steps we reach this point three steps because the weight of this item is three so T of 0 0 is 0 or what is the best value we can do without selecting this or together and that's one so this value is four and this value is once a max of this is 4 all right so the total weight is 4 and the item weight is 3 so again the best I can do is without selecting 3 the best I'm getting is 1 if I do select 3 the best I can again is max off by selecting 3 I get a value of 4 plus I subtract 3 from the 4 so that's that's a 1 and then I go one row up which is 0 and 1 so this value 0 + 1 is 1 so 4 plus 1 5 so max of 4 plus 1 5 or this value 1 so that's 5 again where did this one come from since we selected this item so this item gives us a value of 4 so whatever what is the weight for you're left with the weight you're left with is 1 because this this guy is going to take 4 3 weight and I were told about is 4 so we're left with the weight of 1 and then we check what is the best we can do if we had just wait 1 and we did not include item 3 so that's this guy here which is why we came to this point and the best we can do if we had a weight one twelve eight one and just item 1 is 1 so that's how we get 4 plus 1 5 and the best we can do without including 3 is 1 so we get the max of that so that's 5 all right so 5 here so again we are checking max off either one or weight of value of this guy so that is 4 plus we go up and three steps back 1 1 2 3 and reach this point so this guy so that is 5 so this value will be 5 so it will be 5 all the way to the end so if I had a weight or weight 7 and if I 2 items 1 & 3 the best I can do is by maksim value I can get is five which is pretty much selecting both the items let's include four so since four is less is greater than one this item cannot be picked if the total weight is one so we'll just get the value without including four without including four the best we can do is one similarly one four so here at this point if we pick four we'll get the max off if if we pick four then the best we can do is five plus we go up and four steps back so that's zero or the best we can do without picking four which is five simple the cases you get a value of five so let's go here so here the best I can do is if I'd pick four if I pick item this item the value this item will give me is five plus subtracting subtracting 4 from 5 so we are left with one weight and we're left with two items so if you have one weight and two items that's this value is that value so that's one and then if we did not include four all together the best I can do is 5 so here the max is 6 so I get to get the 6 we get the value if you pick this item so the value of this item is 5 then we go up and we go 4 steps back four steps max because 4 is the weight of this item so 1 2 3 4 and we reach this point so we add that value to this this value so that values 6 so if they do if we group for the best we can do is 6 and if you don't include for the best we can do is 5 so we take 6 here so again for 6 the best we can do is by including this item will be 5 plus going 4 steps back so that's 1 6 or this guy so that's 6 so finally let's look up 4 seven so here if I pick this item with wait for the value I'm getting is max of 4 5 plus going 4 steps back 1 2 3 4 so that's 4 1 2 3 4 so that's 4 or not picking for our together and the best I can do with that is 5 so clearly 9 is bigger than 5 so this becomes none all right so if we had told wait 7 and if we ate three items 1 3 4 the best I can do is 9 so finally let's bring this last row into the picture so since 5 is greater than 1 we cannot improve 5 into the action so we just get the value from the top the best we can do without including 5 so that's 1 so 1 4 5 so here so the best if I include 5 if I include this side the best I can do is max of whatever is the value of 5 so that's 7 plus whatever is left after removing this 5 from the total weight so we are left with 0 so there and then with the 3 I and with other 3 items so we're left with 0 weight and we are left with 3 items so that this guy's a zero or whatever the best we could have done without picking five altogether so that's 6 so here the max is 7 so then we come to this point so again what's the best we can do it for our total weight is 6 if we pick this item with weight 5 I get the value of 7 plus we go 5 steps back 1 2 3 4 5 so 1 but if we don't pick this item 1 together the best I got is 6 so 8 it is better than 6 finally let's come to this point so if I pick this item with weight 5 the value I am getting is 7 plus I subtract 5 from 7 sampler fit to and I'm left with three items so basically we're going five steps back here 1 2 3 4 5 so 1 so 7 + 1 8 or the best we can do without including 5 so that's 9 so here 9 is the winner so this value is 9 so this is a value we can maximum value we can get by picking items from this set such that the total weight is less than or equal to 7 say if someone asked you what is the actual what are the actual items which you are going to fill so let's see how we are going to do that so we'll start from this point here our big our answer and they'll move and will retrace back in this in this matrix and try to find out the actual items so this 9 we are checking where is this 9 coming from this 9 is clearly coming from the top it's not coming from this item it's not coming from this item it's coming from the top it means that since this value is coming from the top it means that this item is not selected if this item was selected this value would not be coming from the top so we know that item with weight 5 is not in the answer then we check where is this 9 coming from so this 9 is clearly not coming from the 5 so this item must be in the answer so item 4 with value 5 must be the answer then so this item is selected then we say where do we go from here so then you go up and we go 4 steps back 1 2 3 4 so this point so from here we directly go to this point since this item is selected it means that it must be taking 4 wait so whatever weight we're left with which is 3 and whatever two items were left with that is where we're going to end up next so that's this point so item with wait for end value 5 is selected then we check where is this guy coming from this guy is not coming from the top so this guy this particular row also must be selected so the item with weight 3 and value 4 is also selected so again now that this item is selected and the weight of this the weight of this item is three so we go up and go three steps back and reach this point as soon as we reach a point where the weight is zero we are done so basically these two items are selected item and the total value here is nine and total weight is seven so tall weight is less than equal to the sum of the weight is less than equal to total weight and the value is maximum next let's look at the formula for this problem so here is my column and J is my eyes my row and J is my column so if J which is my weight is less than weight of I so weight of item I it means that I cannot be caught contributing towards J so our T of I J will be whatever the best we can do without ID which is I minus 1 and J else it means that weight of I is less than equal to j then T of I J will be max of either if item I is included then value of I plus T of I minus 1 and J minus weight of I so if the if item I is included then value of I plus excluding this item and subtract subtracting this the way of this item from the total weight whatever we are left with so that's T of I minus 1 J minus weight on so maximum of this or without including this item all together the best we can do which is T of I minus 1 J so pretty straightforward here if you understand the how the two dimensional matrix is built so this is all I have to talk about Danny about zero-one knapsack problem I asked maybe were to like this video share this video comment of this video check out my Facebook page and check out my github link it up Commission peace interval wiki thanks again for watching this video

37 thoughts on “0/1 Knapsack Problem Dynamic Programming

  1. Though i understood from this video, i had to guess a lot of unexplained things….
    Should have explained all tgose missing things…could do better

  2. This is bottom-up solution. It would be better if you go through Recursion -> Memoize -> Bottom-up approaches.

  3. The first row is not exactly total weight rather it is knapsack size, so if knapsack size is zero we cannot contain any item. If it is one I can have first item, if knapsack size is 3 I can have either first or second item and so on. Also I believe we should first consider what is changing if thief puts item in knapsack e.g. weight will change and capacity of bag will reduce, value will increase and capacity will reduce and so on. Considering all these variables we need to try to reduce the recurrence on our own. IMO that would have been better.

    Also at 15:19 j should have been replaced with w where i (0,1,…i-1) are the items we can pick and w is the weight knapsack can carry.

  4. @tushar Why do we need to run two loops with W and number of items? If the total W is 1000000 and number of items is 3. This loop will still run for 1000001*3 times. In the given example in the video there will be 8*4 = 32 number of calculation. Although it can be done using only 6 number of calculation. I have executed my code with various example and it runs correctly on all the cases.
    Although it takes same space complexity i.e., W*n but we don't have to fill the entire 2D matrix. Please correct if I am wrong.

  5. Just one problem. The 2D array size should be T[total_item+1][total_weight+1]. First Row and First column should be initialized to ZERO.

  6. i really did not understand the max formula… please try to explain it more clearly. I was watching this video before my exam and really got confused.

Leave a Reply

Your email address will not be published. Required fields are marked *