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.

Thank you Mr. Roy, I cannot express just how important it has been to find your upload…

Gus,

London.

Quit Teaching…. Hardest way I've ever seen

Thanks!

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 😀

boht bakwaas samjhate ho

salute you sir wonderful

thank you for your teaching, this really saves me from the hard-reading lecture note.

clear!

Why're you saying THOTAL when you can say total ? ☝

https://www.coursera.org/learn/algorithmic-toolbox/lecture/uYVzW/knapsack-with-repetitions

Their code is neat too!

This is an ok explanation if you already understand it. It's shit if you're trying to understand it for the first time

Best explanation so far

You do a nice job your video is quick short

Which is very reliable at exam time to do learn in minimum time

Thank you

Gandu

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.

SAVED my day

I think you record these vids right before going to work, you look like you are rushing to smwh

I made a video covering this same problem inspired by Tuschar

Bholu pd ley game mt kheel !!

Very good explanation. In my school i was only confused but with your example its simply and clear. Thanks a lot!!!

Making the most easier topic the most complicated one

Totally not satisfied

thanks bro

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

after watching 5min also I dnt get what u trying to explain

Excellent explanation. Thank you, Tushar.

No doubt ,best videos on dynamic programming Tushar Sir.

Well done man, this is a great tutorial.

you talk too fast. I had to slow down the video

咖喱味真的难受

Please be a bit slow with Dynamic programming problems. Thanks

One example : https://www.youtube.com/watch?v=6h6Fi6AQiRM&list=PLbMVogVj5nJSUpKllt0btml02Zsc9U1VU&index=18

Thanks Tushar .. Nice Lecture. Which cam do you use for recording? Please advice.

What if 2 items have the same amount of weight?

fucking noob

I think there is an error in else part that T[ i ][ j ]=max(wt[ i ]+ so on…)

Worst explanation…👎👎

can you try to speak slowly please?

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!

Thank u man I felt difficult to follow u…. But slowly I understood

Could plz make the coding of this problem

Solving my question by 15min comparing my professor by 3 hours…

When filling row 0, your formula gives –

if( 0 < wt[0])

T[0][0]=T[0-1][0];

Isn't something wrong?

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.

thank you for your nice teaching video I totally understand the knapsack problem with your explanation lmfao

Its nice , but u didnot include dynamic programming concept

Expert in confusing students

Thank You!

So I have a 0 1 knapsack mcq and I spend half an hour solving by this method great

How to solve if total wt=40?

@Tushar What if I have 500 weights range from 1 to 1000…In that case will it be array with 500 rows ?

A Space Optimized DP solution for 0-1 Knapsack Problem :: https://bit.ly/2FHw4Dy

It's very great, awesome video, now I become your fun

not get anything in class…

but get everything here..

thanks sir….

Good explanation Sir, Thank you!

how are the items sorted on the table?

you're great man, really appreciate all that you do

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.

Thank you so much please explain the recursive implememntation

1M likes boss…… 1 no.

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

best platform for easy understanding….

worst explanation

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.

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

Thanks ! The Best explanation!!! Keep up the good work!

to work this algorithm well is needed sorted values and weigth array or its not necessarily?

Bilkul padhate nai aata isko…..

Haaye smartness❤️💯

Poor explanation

That's quite clear !

Thanks a lot !

so clear! Thank you so much

thotal no of kholum😂

Gautam gambhir!

Gautam Gambhir bhaiya rocks.

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

What if we have a large maximum weight!? How does the table division take place then!?

Great! Finally spent an hour on this and

All I can say is maybe dynamic programming isn't for me 🙁

thank you sir

very well explained,

1.2 million views OMG!👌

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

You are the best …. thank you sir

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?

king of leetcode

انتا شرحك فاجر والله

Items are sorted accordingly weight or value?

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.

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]);`

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

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();

}

}

thank you so much sir!!!!!!!!!!!!!!

Thanks

how to decide whether to create a 1d or 2d array in dynamic programming question

bc sahi se bna leya kr itna time waste krta ha

this is the best video on knapsack problem on YouTube

Bravo friend thank you very much

do we have to sort the item in advance?

good example. thanks

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

Thanks man, for top-notch explanation.

we will use dynamic programming to solve this problem 😛

sir, tmr is my exam and you have no idea how much this video helped me. thank you so much, from the bottom of my heart.