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 Comments

Code Everyday · March 30, 2019 at 8:50 am

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

Pravallika Kompella · April 1, 2019 at 4:13 pm

How to solve if total wt=40?

Vishali Garg · April 3, 2019 at 10:44 am

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

Thanga · April 4, 2019 at 1:21 am

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

joy chen · April 5, 2019 at 4:12 am

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

kapil kumar · April 10, 2019 at 11:21 am

not get anything in class…
but get everything here..
thanks sir….

chocba1 · April 11, 2019 at 1:24 pm

Good explanation Sir, Thank you!

Jian Jie Liau · April 14, 2019 at 3:07 am

how are the items sorted on the table?

Lifu Tao · April 17, 2019 at 7:40 pm

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

Hargovind Sharma · April 18, 2019 at 5:45 pm

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.

Ashraful Fuad · April 20, 2019 at 6:00 am

Thank you so much please explain the recursive implememntation

PRATEEK SHARMA · April 20, 2019 at 6:59 am

1M likes boss…… 1 no.

Kaushal Kumar · April 20, 2019 at 8:17 pm

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

abhay sharma · April 21, 2019 at 5:55 pm

best platform for easy understanding….

Shaktish Prajapati · April 23, 2019 at 6:50 pm

worst explanation

Akhil Mittal · May 1, 2019 at 2:54 am

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.

Kevin Tran · May 2, 2019 at 6:18 am

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

ronosva · May 2, 2019 at 11:13 am

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

Jakub G · May 3, 2019 at 2:05 am

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

karan khode · May 5, 2019 at 6:12 am

Bilkul padhate nai aata isko…..

INDORI GIRL · May 7, 2019 at 2:37 pm

Haaye smartness❤️💯

Amitesh Rajvaidya · May 11, 2019 at 6:41 am

Poor explanation

蔡皓評 · May 11, 2019 at 7:27 am

That's quite clear !
Thanks a lot !

xianglin yang · May 15, 2019 at 9:05 am

so clear! Thank you so much

Pushkar Soni · May 16, 2019 at 5:45 am

thotal no of kholum😂

EverY ThinG · May 23, 2019 at 1:20 am

Gautam gambhir!

Knowledge Center · May 24, 2019 at 12:15 pm

Gautam Gambhir bhaiya rocks.

Vyshnav Ramesh · May 25, 2019 at 6:48 am

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

Aiswarya · May 28, 2019 at 4:29 am

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

sarthak bansal · June 4, 2019 at 8:55 pm

Great! Finally spent an hour on this and
All I can say is maybe dynamic programming isn't for me 🙁

George tannous · June 9, 2019 at 11:21 pm

thank you sir

Bushra sheikh · June 15, 2019 at 6:19 am

very well explained,

James Kamgar · June 17, 2019 at 9:24 am

1.2 million views OMG!👌

osichi ira · June 19, 2019 at 7:58 pm

You are the best …. thank you sir

Lizzie Daffodil · June 22, 2019 at 9:30 am

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?

lintao Lu · June 23, 2019 at 11:57 pm

king of leetcode

Mohamed Abdelhakem · July 4, 2019 at 8:58 pm

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

Shuvendu Dhal · July 5, 2019 at 10:06 am

Items are sorted accordingly weight or value?

Sanchay Subhedar · July 13, 2019 at 3:21 pm

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.

Sanchay Subhedar · July 13, 2019 at 4:02 pm

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

Puneet Warikoo · July 15, 2019 at 4:07 pm

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

Sarthak Kar · July 15, 2019 at 4:17 pm

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

}

}

Jannatul Ferdous · July 20, 2019 at 9:54 pm

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

Yasin Onur Gürbüz · July 30, 2019 at 10:12 am

Thanks

Abhay Tapadiya · August 1, 2019 at 5:49 pm

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

Devkaran Sharma · August 1, 2019 at 8:03 pm

bc sahi se bna leya kr itna time waste krta ha

Riya Sen · August 2, 2019 at 11:52 pm

this is the best video on knapsack problem on YouTube

loristan gelan · August 5, 2019 at 1:04 pm

Bravo friend thank you very much

Han-Ping Lin · August 8, 2019 at 9:12 pm

do we have to sort the item in advance?

River Wang · August 11, 2019 at 3:15 am

good example. thanks

Akash Bhayekar · August 13, 2019 at 2:42 am

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

Chris Chauhan · August 17, 2019 at 5:24 am

Thanks man, for top-notch explanation.

Jayam Malviya · September 5, 2019 at 6:05 am

we will use dynamic programming to solve this problem 😛

ze MS · September 9, 2019 at 3:29 pm

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.

Daniel Ko · September 13, 2019 at 5:26 am

this changed my life. Best tutorial out there, i grok after only 5 min where many written tutorials failed

Madhu Sudhan · September 16, 2019 at 4:42 pm

Kuch samajh nahi aaya beyy🤦‍♂️😏

Heeramani Prasad · September 19, 2019 at 8:14 am

Very bad explanation, Just like memorized solution.

Sabbir Ahmed · September 22, 2019 at 6:30 am

well explained

A J · September 22, 2019 at 1:37 pm

Sir ,I think first recursive approach should be taught then memoize the repeated sub problems.

Siyao Peng · September 27, 2019 at 2:45 pm

Thanks Tushar, keep up the good work!

Chintan Thakkar · September 29, 2019 at 12:50 am

Do the weights have to be sorted? Because Most of the examples on the internet show the weights, values in sorted order but sorting is not mentioned anywhere?

NIKHIL LINGAM · October 4, 2019 at 5:26 pm

Not clear explanation

Pari Rajaram · October 6, 2019 at 9:41 pm

Explaining the sub problem with recursion would be helpful before you go into 2d table

Vyshnavi Pisupati · October 9, 2019 at 3:54 pm

how does the final answer clearly come from the top can you please explain ?

Prakash Hiranandani · October 13, 2019 at 9:22 pm

Dude you are excellent!!! just excellent!!!

Narendra Parmar · October 21, 2019 at 1:13 pm

Thanks sir

Sabuj Pattanayek · October 22, 2019 at 2:42 am

You can go backwards using value to weight ratios (higest to lowest) stored in a priority queue, if an item doesn't fit you add the next highest item. Then you start from the beginning without using the first item you picked and go down the list by value to weight ratio. You can store the item to value in a hashmap, e.g. {"1,2,3" : sumOfValues} as your dynamic programming lookup so you don't have to do the additions.

Abhishek Kumar · October 25, 2019 at 2:39 pm

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/Knapsack01.java

Levi · October 26, 2019 at 9:40 pm

Great video. The way you draw out the tabulation and go through it very clearly is very helpful.

Lisney M · November 6, 2019 at 6:33 pm

Well… Am I the only one who is still lost? He says "obviously it comes from this" or "it can't be this" and doesn't explain it

I StM I · November 9, 2019 at 8:54 pm

actually a complicated way of explaining it…

side ways · November 16, 2019 at 2:46 pm

one of the best explanations , not just filling the table using the formula 😉

Lekshmi Chidambaram · November 17, 2019 at 2:41 am

Excellent Explanation. Thank you!

ASR MURTHY · November 24, 2019 at 9:26 am

I can do these kind of sums in 30 seconds without any algorithms . Anyway can somebody tel me what was the answer this guy got as all I saw was a table with numbers and crazy signs

Hsin Chen · November 25, 2019 at 1:05 pm

Nice video, thx you

Azadi Bogolubov · November 26, 2019 at 4:56 pm

Best explanation I have seen for this.

Emad Arshad Alam · November 27, 2019 at 7:47 am

the world goes silent when thushar starts thalking.

AMAN PRASAD · November 30, 2019 at 7:31 pm

lund kch smjh ni aya…

Simon Schmitz · December 6, 2019 at 10:09 am

Don't know why the video got so many down votes. For me it is the best video explaining this kind of problem !

mushermusicvevo · December 10, 2019 at 3:12 pm

I think first you need to study before taught us.

jroger181 · December 21, 2019 at 8:23 pm

what is coding solution for finding the items used? he explained, but did not give coding example

aizhan maksatbek · December 23, 2019 at 10:00 pm

very clear

Manish Thakur · December 25, 2019 at 4:29 pm

you ask yours viewers a little too much in the end, doncha? 15:38

Shih-Min Lee · December 30, 2019 at 4:58 pm

very clear explaination.

Hasham Akram · January 5, 2020 at 8:28 am

Fazool

harsha kumar Reddy · January 8, 2020 at 9:41 am

What to do when there is multiple objects of same type and one is not allowed to choose fractions.

Abhinav Tiwari · January 12, 2020 at 1:28 pm

Something is wrong with the caption at 1:28

Rajat Bajaj · January 19, 2020 at 11:58 am

This man is more confused about the problem statement than my 6 month old shihtzu

Manu Gupta · January 20, 2020 at 2:08 pm

Sir can you please tell the code how to determine the actual elements which were included in the sum which we found out.

MisterAadj · January 20, 2020 at 2:48 pm

great explanation!!

Li-Jie Tang · January 23, 2020 at 6:50 pm

Thank you man. Nice video

Dihyan Fauzana · January 27, 2020 at 4:43 am

Nice, so useful

Saffaura · February 1, 2020 at 12:50 am

we must protecc this wise coder from ww3 🙏

Cojocaru Cosmin · February 2, 2020 at 8:25 pm

You re really good man, really really good

Saksham Prakash Music · February 9, 2020 at 4:29 pm

you need to take a nap brother

Alpesh Jamgade · February 14, 2020 at 3:23 pm

thank you

Wenjin Zhang · February 14, 2020 at 9:35 pm

Thank you so much you totally saved my life.

Sushil Jaiswal · February 17, 2020 at 6:02 pm

Thank you so much Gautam Gambhir..!!

TheGamingHydra · February 20, 2020 at 1:25 am

extremely helpful

Yuan Li · March 1, 2020 at 12:46 am

Thanks! very clear

Leave a Reply

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