0/1 Knapsack Problem Dynamic Programming

0/1 Knapsack Problem Dynamic Programming


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

100 thoughts on “0/1 Knapsack Problem Dynamic Programming”

  1. I don't know how to thank you without sounding like I'm exageratting
    my biggest struggle never was the probblem itself but the… "traceback" so to speak
    I always tried to keep record of the selected items in the same matrix and it cracked my head beacause it seemed so innefficient

    THANK YOU times a thousand 😀

  2. In the matrix at T[3][7] can't you choose 2 3's to get 8 + 1 = 9. So that solution of 5 that you have on the board isn't optimal? Or am I misunderstanding.

  3. How did you arrive to T[0][0], I can understand first zero, but second one is not clear. https://youtu.be/8LusJS5-AGo?list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&t=254

  4. Please be a bit slow with Dynamic programming problems. Thanks
    One example : https://www.youtube.com/watch?v=6h6Fi6AQiRM&list=PLbMVogVj5nJSUpKllt0btml02Zsc9U1VU&index=18

  5. Goran Stefanovski

    I have one question, what is criteria for sorting items, by value or by weight? I guess it is important. I cannot figure it out from the example. Great tutorial, thanks!

  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.

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

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

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

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

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

  12. Hello! If we have total wt 8 and wt-2 val-1, wt-3 val-2, wt-4 val-5, wt-5 val-6 how the table will look like? I have exams tomorrow and I need your help. Thank you

  13. well explained! but how do we construct a formula in dynamic programming, like the one we have in the knapsack problem? Each dp problem comes up with some tricky problem. Is there a trick to crack the formula from the question?

  14. I like the video. Super helpful. Two things though, I would have loved to see a list of few questions which can be solved using 0/1 Knapsack. Also, in the second part of the video where you explain the formula, it would have been easier to understand if you could have used variable names as row and column instead of i,j.

  15. Also, in the bottom up approach in github code, the line `K[i][j] = Math.max(K[i-1][j], K[i-1][j-wt[i-1]] + val[i-1]);` is incorrect. It should be `K[i][j] = Math.max(K[i-1][j], K[i-1][j-wt[i-1]] + val[i]);`

  16. @Tushar Roy: How can we find multiple sets if calculating to the same final output? LIke if you have duplicates

  17. knapSack Code in Java, it includes printing the weights and values that are taken to maximize the result
    import java.io.BufferedReader;

    import java.io.BufferedWriter;

    import java.io.IOException;

    import java.io.InputStreamReader;

    import java.io.OutputStreamWriter;

    import java.util.ArrayList;

    public class KnapSack {

    static ArrayList<ArrayList<Integer>> findKnapSack(int[] weight,int[] values,int weightLimit) {

    int[][] knapSack = new int[weight.length][weightLimit + 1];

    for(int i = 0;i < weight.length;i++) {

    for(int j = 1;j <= weightLimit;j++) {

    if(i == 0) {

    if(j < weight[i]) {

    knapSack[i][j] = 0;

    }else {

    knapSack[i][j] = values[i];

    }

    }else if(j < weight[i]) {

    knapSack[i][j] = knapSack[i – 1][j];

    }else {

    knapSack[i][j] = Math.max(values[i] + knapSack[i – 1][j – weight[i]], knapSack[i – 1][j]);

    }

    }

    }

    ArrayList<Integer> al = new ArrayList<>();

    ArrayList<Integer> al1 = new ArrayList<>();

    //adding the selected values and weights to the ArrayList
    int row = weight.length – 1,col = weightLimit;

    while(knapSack[row][col] != 0) {

    if(row == 0 && col != 0) {

    al.add(values[row]);

    al1.add(weight[row]);

    row = 0;

    col = 0;

    continue;

    }

    if(knapSack[row][col] != knapSack[row – 1][col]) {

    al.add(values[row]);

    al1.add(weight[row]);

    col = col – weight[row];

    }

    row–;

    }

    ArrayList<ArrayList<Integer>> p = new ArrayList<>();

    p.add(al);

    p.add(al1);

    return p;

    }

    public static void main(String[] args)throws IOException {

    // TODO Auto-generated method stub

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] weight = br.readLine().split("\s+");

    String[] values = br.readLine().split("\s+");

    int weightLimit = Integer.parseInt(br.readLine());

    int[] weightArr = new int[weight.length];

    int[] valuesArr = new int[values.length];

    for(int i = 0;i < weight.length;i++) {

    weightArr[i] = Integer.parseInt(weight[i]);

    valuesArr[i] = Integer.parseInt(values[i]);

    }

    //printing the selected weights and values
    ArrayList<ArrayList<Integer>> ans = findKnapSack(weightArr, valuesArr, weightLimit);

    for(ArrayList<Integer> al : ans) {

    for(Integer k : al) {

    bw.write(k+" ");

    }

    bw.write("n");

    }

    bw.flush();

    }

    }

  18. How to solve it if max weight is very high like in thousands.. we can't create matrix for thay high weight.. any other optimization

Leave a Reply

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