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.
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.