Hello friends my name is Tushar and today I'm going to talk about 0/1 knapsack problem So I have an old video on this question but I felt I missed few things in that video so I am 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 sum of their weights is
less than or equal to the 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 0/1 knapsack problem just say that you could have split the item.There's a greedy solution to solve the question.All you have to do
is sort the item by their value to weight,sort the items by their 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/1 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 to pick
24
00:01:28,960 --> 00:01:28,192
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 from the total
weight and excluding this item or the best
you can do without including this item or together Let's try to understand on with this
example.So here i have a two dimensional matrix and this is a my total number of columns is same as
total weight plus one 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 zero
no matter what items I have my maximum value I can get is
always zero. So this is why this all are zero. So let's start from here,so if my total weight was 1 and if I just had one item 1, the best I
can do is 1. So this is the weight of item, the total weight is one. so the maximum value I can get is just 1. If my total weight is two, 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 item. So even though the total weight is 2 if
I just have item 1 again the best I can do is value 1.Similarly one one one one one. So if the total weight is 7 the only item I have is weight 1 and whose value is 1 the best I can do is one 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 one so three can never be the, can
never be selected. So what we do is what is the best
we can do without selecting 3 so basically this number becomes one.
Again 2 Since 2 is less than 3, 3 can never be
selected.Since this 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
equal to 3, we have 2 choices, do we select 3 or do
we not select 3 If we select this item the so we have to check what is the best we
can do by selecting this item. If we didn't select this item this gives me a
value 4 plus whatever weight is remaining after we select this
weight. So 3 -3 so that's 0. So t[0] and then and then we go to the top column so
that's also 0. So we reach this point,so we up,we go 3 steps, we reach this point,3 steps because the weight of this item is 3 So T[0][0] is 0 or what is the best value we can do without selecting this item altogether and
that's 1. So this value is 4 and this value is 1 so max of this is 4. Alright, 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
get is max of by selecting 3 I get a value of 4 plus I subtract 3 from 4 so that's,that's 1. and then I go one row up which is 0 and 1. So this value 0 and 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 1 came from? Since we selected this item so this item gives us a value 4 .So
whatever, what is the weight we are left with your left the weight we are left with is 1 because this guy is
gonna take 3 weight and our total weight is 4. So we are left with weight of 1 and then we check what is the best we
can do if we had just weight 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 1, total weight 1 and
just had a 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.Alright,so 5 here,so again we are checking max of either 1 or weight of value of this guy so that's 4
plus we go up and 3 steps back. 1,1,2,3 and reach this point. so this guy,so that's 5. So this
value will be 5,so it will be 5 all the way till the end.So if I had a weight,total weight 7 and if I had 2 items 1 and 3 the best I
can do is max value I can get is 5 which is pretty
much selecting both the items. Let's include 4 so since 4 is greater than 1, this
item cannot be picked if the total weight is 1. So we'll just
get the value without including 4. Without including
4, the best we can do is 1. Similarly 1,4. So here at this point if we pick 4 we'll get the max of,if we pick 4 then the best we can do is
5 plus we go up and 4 steps back and that's 0 or the best we can do without picking 4
,which is 5.So in both the cases we get a value 5. So that's go here. So here the best I can do is if I pick 4 if I pick item this item the value this item will give me is 5 plus subtracting,subtracting 4 from 5
so we are left with 1 weight and we are left with 2 items so if we have 1 weight and 2 items that's
this value is that value so that's 1 and then if we did not include 4 altogether the best I can do is 5 so here the max is 6 so I need to get this 6 We get the value we pick this item so the value of this item is 5 then we go up and we go 4 steps back. 4 steps back because 4 is the weight of this item.1 2 3 4 and we reach this point so we add that value
to this this value so that value is 6 so if we,if we include 4 the best we can do is 6 and if we don't include 4 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 lets look up for 7 So here if I pick this item with weight 4
the value I'm getting is max of 4,5 plus going four steps back 1 2 3 4 so that's 4. 1 2 3 4 so that's 4. or not picking 4 altogether and the
best I can do with that is 5. So clearly 9 is bigger than 5, so
this becomes 9. Alright so if we had total weight 7 and if we had 3 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 include 5 into the action so we just get the
value from the top so 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 could decide 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 items,with other 3 items so we are left with 0 weight and we are left with 3 items so that's this guy,so 0 or whatever the best we could have done without picking 5 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 if 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 and if we don't pick this item altogether the best I got is 6. So 8. 8 is better than 6.Finally let's come to this point so if I pick
this item with weight 5 the value I'm getting is 7 plus I subtract 5 from 7 so I'm left with 2 and I'm left with 3 items so basically we are going 5 steps back
here 1,2,3,4,5 So 1 so 7 plus 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.So if someone asks you what is the
actual,what are the actual items which we are going to pick? So let's see how we're going to do that.
So we start from this point here our big,our answer and we'll move and we'll retrace back in this,in this matrix and try to find out the actual items.So this 9 we're 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's this 9 coming
from. So this nine 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 we go up and 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 weight so whatever
weight we're left with which is 3 and whatever 2 items we are left that is where we're gonna end up next. So that's this point.So item with weight 4 and value 5 is selected. Then we check where's 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 time is selected and the weight of this,the weight of
this item is 3 so we go up and go 3
steps back and reach this point. As soon as we reach
a point where the weight is 0 we are done. So basically these 2 items are our selected items and
the total value here is 9 and total weight is 7 so total 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 i is my column and j is
my, i is my row and j is my column so if j which is my weight is less then weight of i so weight of item i,it means that i cannot be contributing towards
j so our T of i,j will be whatever the best we can do
without i which is i-1 and j as it means that weight of I is less than equal to j then T[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 subtracting this,the weight of this item from total weight whatever we are left with so that's T[i-1] [j-wt[i]) so maximum of this or without including this item altogether the best we can do which is T[i-1][j] so pretty straight forward here if you
understand the, how the 2 dimensional matrix is built. built.So this is all i have to talk about 0/1 knapsack problem. I ask my viewer to like this video,share this video,comment on this video. Check out my facebook page and checkout my github link github.com/missionpeace/interview/wiki. Thanks again for watching this
video.
