We all know, this is not practical, I am aditya I am from NIT and I got placed at flipkart you can watch my DP playlist. Just watch from the very starting and I can promise you, you wont be disappointed. th-cam.com/video/nqowUJzG-iM/w-d-xo.html
Very nice, became a fan of you. best online teacher I have ever found. plz keep making video like this, the new generation student will be benefited.. Thank you..
Amazing videos man. Like Sal Khan (founder of Khan academy), you have a unique knack for teaching extremely complex concepts. I have learnt so much from your videos. Thank you once again!!
I spent 2 whole days trying to understand 0-1 knapsack problem until I stumbled upon this video. This video explains more than just arriving on a mathematical equation. Many thanks for making this video.
@Tushar Roy, we need more teachers like you. Your virtues: your videos are well paced unlike many other indian videos, which keeps a person interested, no extraneous content -- everything is precise and to the point (extremely helpful) at times while revising concepts. I wish you all the best for your future endeavours. Wish I could meet you some day personally for your autograph. Thanks a lot for your efforts, you are just amazing!! :)
Thanks a lot for explanation.. I finally understood the algorithm. I have just one suggestion ,you should have 0th column also so that you have its row(top row) with all 0s.I got little bit lost :) with your explanation when you said for the first column with weight 1 that best we can do is 1 (for weight 0 to 7). If you had the top row (with 0s) you could have applied the max formula and shown everyone why each value ended up being 1 (like you did with other three items). The reason I mentioned this is because while writing a computer program we need the top row with 0s in order to make the max formula work for 1st item. But again thanks a lot.. :)
Hey Tushar , Many many thanks for doing such a wonderful job of explanining dynamic programming problems in such a lucid way!!. Kudos to you. However in your videos I find one little thing missing and thats is how you arrive at the optimal substructure property of a given example ( which IMO is the crux for nailing down new dyn problems). Like you directly start solving the probem by drawing a 2D /1D array, process of filling the array and then writing down the recurrence at the very end. It would be really helpful if you could spend time in discussing the thorught process to approach the problem first which will really help listeners to develop a knack of solving new dyn problems. As a very specific example , in this video , before even we start to solve the knapsack problem, discussing the optimal substructure property linguistically like : The maximum value that can be obtained from n items is max of following two values. 1) Maximum value obtained by n-1 items and W weight (excluding nth item). 2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item). If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility. would have been really useful. Thanks again for such a wonderful job!!
bro this is not about teaching you about how to think atleast most of the times it is not what he provides in his videos. he rather just teaches interview question that can be asked in straight interviews. if you want to think of how is it done may be someone can teach you that but it would be of no use cause next time you will be stuck again. you need to think yourself it may take a day , two or a week or even longer but until you are the only guy who clears your concept, you wont get what you want. i had this mentor of mine who told me that in a problem he had to use 6d dp can you imagine ? yeah 6d dp he kept thinking about it for about half a month or even more and he finally got his solution accepted it is just about thinking and just thinking bruv.
Your videos are so good! I skipped nearly all the lectures for algorithms class this semester cuz I know you'll explain it better than my prof. Thank you Tushar!
Cool to know it...DP is a lovely programming technique to solve complex problem...here's one more video on the same problem of Knapsack explaining everything in quite detail th-cam.com/video/9EkZ2V7Tiew/w-d-xo.html
In one word Nice.. I have no objection to tell you sir because you are one of my best teacher in youtube. Sir we need more.Please sir you have the ability.We need more from you..
BEST TUTORIAL EVER!!!! !!! I have watched so many tutorials i didn't understand anythything, that T[0][0] thing helped me understood... others just keep saying ith ith idiots. THis is the best, you are the best!!!
It would have been still better if he had written MAX ( 1) currentItem's value + T[one_row_up=0][3-3=remaining weight's index] which gives the maximum value for remaining available weight considering all the previous lesser weighted items OR 2) T[one_row_up][same_column] which gives the value considering all the previous lesser weighted items ) . If 2) is chosen, then it means the current item is not chosen for the weight considered at the moment. Of course T[0][0] triggered the thinking process immediately! Just watch 3 or 4 times until you understand and dwell on the logic in your mind to satisfy your intuition completely and for retaining the reasoning why this logic works.
Your explanation did provide the nice insight into why we are going back in the previous row while calculating max. Thanks for the explanation and nice video indeed.
No, brother. Even I had quitted dynamic programming in the middle because I wasn't able to understand anything. but now, I can proudly say that dynamic programming is very intersting topic. So, don't loose your hope, just take some break from dynamic proggramming and resatrt it.
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.
I am aditya I am from NIT and I got placed at flipkart you can watch my DP playlist. Just watch from the very starting and I can promise you, you wont be disappointed. th-cam.com/video/nqowUJzG-iM/w-d-xo.html
For people who are asking about intuition and to explain why does he go up and left. This is what is the crux of DP. It's called memoization. For example, let's see the point where you have 1,3 and 4 weights and w=7 at 8:49. Now you have two choices: 1. Use 4 If you use 4, then you are left with 7-4=3 total knapsack size and 1 and 3 as remaining weights available to you. Now the question can be rephrased as "you have a knapsack of size 3 and 1, 3 wights, available, give me the optimal total value". This is where memoization comes into picture, you have already solved this subproblem and you already have an optimal solution for it i.e optimal value = 4. That is what basically he is doing by going up and left at t[1][3] 2. Do no use 4 Again question becomes, you have a total knapsack of size 7 and two wegiths of size 1 and 3, give optimal value. We have already solved this sub problem as well. It's 5 (t[1][7])
Thanks, this helped add a bit more clarity to the process, coming from a different video. However, despite both myself and so many people getting this and applauding it, I wouldn't be surprised if some people were confused a bit or mislead on account of some particulars. I'd like to offer some clarity for any such person that's out there: 1) In the context of what this process represents, it's a bit misleading to use the term "Total Weight" where you did here. This may not have been misunderstood by most, but I can see some people either being confused by it or mislead without them even realizing it. The 7 does not represent the total weight of the items chosen but instead is the *Capacity* aka *Weight Limit* aka *Maximum "Space" Available of the knapsack/container* being considered. As you proceed through these columns, you are allowed higher and higher available Weight Limits, which will *not necessarily* be equal to the total weight of the items selected. 2) It would be a bit clearer and quicker to comprehend if you referred to each item by its Item Number, instead of saying things like "item 3" in reference to the item that has a weight of 3..or "item 3" in reference to the item that has a value of 3. I think you referred to items interchangeably in this way a couple of times, then wrote the Value and Weight in reverse order towards the end. These are little things, but it can make the difference for some people. Anyone that's following the concept can read between the lines and look past these things, but someone that's trying to hone in the details without exception may misinterpret the opposite of what you mean at certain points. Sorry but it's a bit of a pet peeve of mine when nomenclature isn't consistent throughout a lecture, much like the need for a textbook to be consistent with its notation throughout any given problem at least. Just some constructive criticism. Thank you
If anyone hers to learn DP and has fear for DP .. please avoid this sway of learning..... you should learn DP with recursive tree ----> memorization ----> Top down..... please please draw Recursive tree in pen and paper.. else whole life you will fear this sshit........
The power of explaining the same thing over and over, but in the most fundamental way. Helps me understand a lot, because I can pause the video and try to understand what he is saying. I am also motivated to pause and ponder because I know that was he is saying is correct!
First i watched MIT's video , didnt understand, and seriously after watching this whole funda has been cleared with ur explanation of formula. Hats off!!!!
You completely didn't explain how the re-trace to find out which items are included works. How do you know whether to move up or to the side in the matrix? You only said "it's obviously not coming from x" but didn't explain why.
I hardly think so, let's say the max method max(4 + 1, 5) obviously returns 5, but how could we know the value 5 comes from the upper position or the value itself.So in that case there are 2 results, ain't there? I don't say he's wrong, I think it's just not completely right.
starting from n , tw : just check if ( T[i][j] == T[i-1][j]) // we didn't pick the i-th item and we go to T[ i - 1 ][ j ] else // we picked the i-th item print it and go to T[ i - 1 ][ j - weight[ i ] ] until we reach a zero
hi Tushar, thanks for one more good video!! m = Total_weight, n is size of wt/val array. Time: O(m*n), Space: O(m*n) ( Correct me , If i'm wrong ) If total_wt is say, 1000. then we would need to 1000 columns to solved this problem?? Is there a way to optimise further??
Let's say you have a basket that can hold 7 kg and you selected an item that is 4 kg weight which gives the value of 6 (best value). After selecting the weight of 4 kg, your basket can still hold 3 more kgs. For that if you go up and 4 steps to left (which means 7-4=3) , you will end up getting the best value that you had found for the remaining 3 kgs (which you had already calculated before coming to the place/row where you selected the 4 kg).
+Tushar Roy oh sorry I forgot to mention after I solved coin change problem by watching your video I understood both coin change and knapsack. thank you very much.
+Sandesh Avhad I haven't tested it but I believe you can do this while(i>=0||j>=0) then choose the maximum of the two print it and then alter the values of i and j accordingly
To the guys whose comments got deleted due to abuse. Instead of abusing maker of the video try to understand the topic (if you really wish to learn something)
You my good sir, are an excellent instructor! Accept my deepest gratitude for saving my ass as I couldn't make heads or tails of this particular algorithm until i stumbled upon your tutorial.
try seeing the complete video and watch every iteration. I didnt understand in the starting but then when he came to the third row, that was the time things suddenly started becoming clear.
It's all practice. You should check out blind programmers, they listen to their code being read out, and they work at a similar speed to seeing programmers. Insane talking speeds.
No. How can u get an total value of 8, when your capacity in that column is only 6. There are only two possible ways: put in weight 4+1 (value 6) or 3+1(value 5). Or look at this approach: If you take weight 4 with value 5, you still have weight left, therefore you go one row up and go 4 columns to the left => 5+1 = value 6
vedant bhagwat he is teaching like a pro. if u don't understand simple algorithm do not jump on to dynamic programming . first get use to simple algorithm then go for dynamic programming.
@@joeystechpluscode Thank you Joey, I just checked, and your videos are really good too. I think you guys have different viewers though. I have already read and studied and understood these problems once in my life, and I just need to review all of them with a fast pace in a short time to get ready for an interview. Your videos are a bit slow for me. But I would suggest them to any friend who are looking to understand the problem and solution.
After 8 years, still so much better than our computer science teachers. Thank you for the video.
-Turkey
This is the THIRD video I've watched on the Knapsack problem and the ONLY one that helped me understand it. Thank you so much for sharing this!
Thank you Mr. Roy, I cannot express just how important it has been to find your upload...
Gus,
London.
I finally see it, 2 years after I learnt my algorithm class. Thank you.
please check this playlist : th-cam.com/play/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr.html
@@shashanksagarjha2807 wish that playlist could be in english man
nice video gautam gambhir
:D
🤣🤣🤣
We all know, this is not practical, I am aditya I am from NIT and I got placed at flipkart you can watch my DP playlist. Just watch from the very starting and I can promise you, you wont be disappointed.
th-cam.com/video/nqowUJzG-iM/w-d-xo.html
@@TheAdityaVerma I agree
ha hah
Nicely put! Thanks for the explanation. It's great that you take an example and go through the problem step by step. Keep up the good work! :)
please watch this playlist for detailed explanation of dynamic programming..th-cam.com/play/PLeF0b8iqbx4mTBJZ5ukIYj92_B4k2L1-8.html..
please check this playlist : th-cam.com/play/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr.html
Best 0/1 Knapsack tut on the Internet! Keep up the good work! :)
Ever heard of Abdul Bari ?
@@kairatopa9564 ever heard of aditya verma
No way..this is like memoization of algorithms, I definitely recommend Aditya's approach
@@nagarjuna119 absolutely
this video finally ended my hunt to find a video which explains me knapsack perfectly
It's far better than 90% videos available on the same topic + you cover the basics... Keep up the good work !🤘
You seem to have watched all the videos on platform on this topic.
After 9 years, this video is still so much helpful, Thank you!
Very nice, became a fan of you. best online teacher I have ever found. plz keep making video like this, the new generation student will be benefited.. Thank you..
Thanks Tushar Roy for your simple way in teaching and your best way in delivering the main idea of the Algorithm
Tushar, THANK YOU!!!!
This was a great explanation. I wish my class material was as clear as this.
Great video. The way you draw out the tabulation and go through it very clearly is very helpful.
Amazing videos man. Like Sal Khan (founder of Khan academy), you have a unique knack for teaching extremely complex concepts. I have learnt so much from your videos. Thank you once again!!
waste fellow nt explaining correctly nt suit for beginners waste fellow tushora
first video that made me understand the knapsack problem and the code!!! thank you!
Best tutorial on the 0-1 knapsack problem that I ever saw. Thanks!
I can't agree with u anymore!!!
that basically means you disagree with him.
no that basically means he used to agree with him but now he diasgrees ...time changes
I can't agree with you more
agree or disagree
I spent 2 whole days trying to understand 0-1 knapsack problem until I stumbled upon this video. This video explains more than just arriving on a mathematical equation. Many thanks for making this video.
@Tushar Roy, we need more teachers like you. Your virtues: your videos are well paced unlike many other indian videos, which keeps a person interested, no extraneous content -- everything is precise and to the point (extremely helpful) at times while revising concepts. I wish you all the best for your future endeavours. Wish I could meet you some day personally for your autograph. Thanks a lot for your efforts, you are just amazing!! :)
You are really doing a great job. Because of you , people are learning tough concepts so easily and getting good jobs . Keep it up tushar :)
For those who are having trouble understanding how the table is generated; for me it helped the most to carefully listen from 8:15 to about 8:45
Superb! Much better than my Algorithm teacher in Uni, thank you very much!
Thanks a lot for explanation.. I finally understood the algorithm.
I have just one suggestion ,you should have 0th column also so that you have its row(top row) with all 0s.I got little bit lost :) with your explanation when you said for the first column with weight 1 that best we can do is 1 (for weight 0 to 7). If you had the top row (with 0s) you could have applied the max formula and shown everyone why each value ended up being 1 (like you did with other three items). The reason I mentioned this is because while writing a computer program we need the top row with 0s in order to make the max formula work for 1st item.
But again thanks a lot.. :)
thank you random indian person behind my screen for teaching me how to solve this quite magic riddle
Hey Tushar , Many many thanks for doing such a wonderful job of explanining dynamic programming problems in such a lucid way!!. Kudos to you. However in your videos I find one little thing missing and thats is how you arrive at the optimal substructure property of a given example ( which IMO is the crux for nailing down new dyn problems). Like you directly start solving the probem by drawing a 2D /1D array, process of filling the array and then writing down the recurrence at the very end. It would be really helpful if you could spend time in discussing the thorught process to approach the problem first which will really help listeners to develop a knack of solving new dyn problems. As a very specific example , in this video , before even we start to solve the knapsack problem, discussing the optimal substructure property linguistically like :
The maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
would have been really useful.
Thanks again for such a wonderful job!!
usko bhi nhi samajh aata bhai'
Yes this is what I am looking for
You Sir, are great.
NAVEEN OJHA he is an employee of apple!!!
bro this is not about teaching you about how to think atleast most of the times it is not what he provides in his videos.
he rather just teaches interview question that can be asked in straight interviews.
if you want to think of how is it done may be someone can teach you that but it would be of no use cause next time you will be stuck again.
you need to think yourself it may take a day , two or a week or even longer but until you are the only guy who clears your concept, you wont get what you want.
i had this mentor of mine who told me that in a problem he had to use 6d dp can you imagine ? yeah 6d dp
he kept thinking about it for about half a month or even more and he finally got his solution accepted it is just about thinking and just thinking bruv.
Excellent video Tushar. I never understood this properly in my Masters, but you are way too good. Thanks !
Your videos are so good! I skipped nearly all the lectures for algorithms class this semester cuz I know you'll explain it better than my prof. Thank you Tushar!
Was struggling with this example in my algorithms class and this dynamic programming playlist is gold.
This is the exact same problem I got on my final algorithmics exam. God bless you!
Cool to know it...DP is a lovely programming technique to solve complex problem...here's one more video on the same problem of Knapsack explaining everything in quite detail th-cam.com/video/9EkZ2V7Tiew/w-d-xo.html
University of Southampton: FBI OPEN UP!
this changed my life. Best tutorial out there, i grok after only 5 min where many written tutorials failed
the world goes silent when thushar starts thalking.
🤣🤣🤣🤣
sir your way of teaching is too good ....i didnt get bored in any part of ur video..thank you
Thanks man! I wished I had a teacher like you when I had my first algorithms class.
I wish*
Thanks jayesh
In one word Nice.. I have no objection to tell you sir because you are one of my best teacher in youtube. Sir we need more.Please sir you have the ability.We need more from you..
BEST TUTORIAL EVER!!!! !!! I have watched so many tutorials i didn't understand anythything, that T[0][0] thing helped me understood... others just keep saying ith ith idiots. THis is the best, you are the best!!!
I totally agree with you.
It would have been still better if he had written
MAX (
1) currentItem's value + T[one_row_up=0][3-3=remaining weight's index] which gives the maximum value for remaining available weight considering all the previous lesser weighted items
OR
2) T[one_row_up][same_column] which gives the value considering all the previous lesser weighted items
) .
If 2) is chosen, then it means the current item is not chosen for the weight considered at the moment.
Of course T[0][0] triggered the thinking process immediately! Just watch 3 or 4 times until you understand and dwell on the logic in your mind to satisfy your intuition completely and for retaining the reasoning why this logic works.
Love you Tushar sir.... 0/1 Knapsack became very easy to understand after watching the video tutorial.
Solving my question by 15min comparing my professor by 3 hours...
Your explanation did provide the nice insight into why we are going back in the previous row while calculating max. Thanks for the explanation and nice video indeed.
Great! Finally spent an hour on this and
All I can say is maybe dynamic programming isn't for me :(
No, brother. Even I had quitted dynamic programming in the middle because I wasn't able to understand anything.
but now, I can proudly say that dynamic programming is very intersting topic. So, don't loose your hope, just take some break from dynamic proggramming and resatrt it.
XD
please watch this playlist for detailed explanation of dynamic programming..th-cam.com/play/PLeF0b8iqbx4mTBJZ5ukIYj92_B4k2L1-8.html..
It is the best tutorial of the Knapsack.I'm very thankful for you Tushar
one of the best explanations , not just filling the table using the formula ;)
I tried two other videos before finding this one. Much clearer explanation than the others I tried. Thank you.
You'll find a more clear and easy to understand explanation on joey'sTech th-cam.com/video/nfUNBWFuFoY/w-d-xo.html
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.
I am aditya I am from NIT and I got placed at flipkart you can watch my DP playlist. Just watch from the very starting and I can promise you, you wont be disappointed.
th-cam.com/video/nqowUJzG-iM/w-d-xo.html
@@TheAdityaVerma I hope more people see this.
@@TheAdityaVerma I have watched your Binary search playlist and they are really good. Great job!
bro i didn't learn like this from anybody else, what a simple way of explaining!!
For people who are asking about intuition and to explain why does he go up and left. This is what is the crux of DP. It's called memoization. For example, let's see the point where you have 1,3 and 4 weights and w=7 at 8:49. Now you have two choices:
1. Use 4
If you use 4, then you are left with 7-4=3 total knapsack size and 1 and 3 as remaining weights available to you. Now the question can be rephrased as "you have a knapsack of size 3 and 1, 3 wights, available, give me the optimal total value". This is where memoization comes into picture, you have already solved this subproblem and you already have an optimal solution for it i.e optimal value = 4. That is what basically he is doing by going up and left at t[1][3]
2. Do no use 4
Again question becomes, you have a total knapsack of size 7 and two wegiths of size 1 and 3, give optimal value. We have already solved this sub problem as well. It's 5 (t[1][7])
Thanks, this helped add a bit more clarity to the process, coming from a different video. However, despite both myself and so many people getting this and applauding it, I wouldn't be surprised if some people were confused a bit or mislead on account of some particulars. I'd like to offer some clarity for any such person that's out there:
1) In the context of what this process represents, it's a bit misleading to use the term "Total Weight" where you did here. This may not have been misunderstood by most, but I can see some people either being confused by it or mislead without them even realizing it. The 7 does not represent the total weight of the items chosen but instead is the *Capacity* aka *Weight Limit* aka *Maximum "Space" Available of the knapsack/container* being considered. As you proceed through these columns, you are allowed higher and higher available Weight Limits, which will *not necessarily* be equal to the total weight of the items selected.
2) It would be a bit clearer and quicker to comprehend if you referred to each item by its Item Number, instead of saying things like "item 3" in reference to the item that has a weight of 3..or "item 3" in reference to the item that has a value of 3. I think you referred to items interchangeably in this way a couple of times, then wrote the Value and Weight in reverse order towards the end.
These are little things, but it can make the difference for some people. Anyone that's following the concept can read between the lines and look past these things, but someone that's trying to hone in the details without exception may misinterpret the opposite of what you mean at certain points. Sorry but it's a bit of a pet peeve of mine when nomenclature isn't consistent throughout a lecture, much like the need for a textbook to be consistent with its notation throughout any given problem at least.
Just some constructive criticism. Thank you
Thanks, helped me prepare for final exams! Greeting from Prague.
I can't stop seeing your videos!!! You are simply awesome....and it's of course the best video as far as 0-1 knapsack prob is concerned!!!
If anyone hers to learn DP and has fear for DP .. please avoid this sway of learning..... you should learn DP with recursive tree ----> memorization ----> Top down..... please please draw Recursive tree in pen and paper.. else whole life you will fear this sshit........
Thank you my bro ❤❤❤
By far the best explanation about knapsack algorithm I 've seen on youtube. Great job!
Sir ,I think first recursive approach should be taught then memoize the repeated sub problems.
you forgot the 0th row. that is very critical for this to work. thanks for your amazing videos.
Hi Tushar... Your method is so simple. Easy to understand some complex DP problems. Thanks..
your timely verbal explanation is superb.
0:13 Gyaps ?
The power of explaining the same thing over and over, but in the most fundamental way. Helps me understand a lot, because I can pause the video and try to understand what he is saying. I am also motivated to pause and ponder because I know that was he is saying is correct!
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.
not compulsory ... u can do as it is explained too ...i did it n it got execute successfully
First i watched MIT's video , didnt understand, and seriously after watching this whole funda has been cleared with ur explanation of formula. Hats off!!!!
Tau ye bhi bata dia kro ki DP ku lagani hai
Bs "Yes we will use dynamic programming for this solution"
ye to keetab bhi bata deti hai
Well said
true man
Bilkul bhai, is table ko bna kr dara or dete hai
th-cam.com/video/nqowUJzG-iM/w-d-xo.html
Very good explanation. In my school i was only confused but with your example its simply and clear. Thanks a lot!!!
You completely didn't explain how the re-trace to find out which items are included works. How do you know whether to move up or to the side in the matrix? You only said "it's obviously not coming from x" but didn't explain why.
Every value is actually maximum of value above it and some other value. When value is same as one above then it's obvious where it came from.
I hardly think so, let's say the max method max(4 + 1, 5) obviously returns 5, but how could we know the value 5 comes from the upper position or the value itself.So in that case there are 2 results, ain't there? I don't say he's wrong, I think it's just not completely right.
You're completely right that he isn't. :)
look closely to the if else condition
starting from n , tw : just check if ( T[i][j] == T[i-1][j]) // we didn't pick the i-th item and we go to T[ i - 1 ][ j ]
else // we picked the i-th item print it and go to T[ i - 1 ][ j - weight[ i ] ]
until we reach a zero
awesome video.....very nice explanation.....
This is coming from a student of IIIT Hyderabad....u explain better than my prof....keep it up!!
hi Tushar, thanks for one more good video!!
m = Total_weight, n is size of wt/val array.
Time: O(m*n), Space: O(m*n) ( Correct me , If i'm wrong )
If total_wt is say, 1000. then we would need to 1000 columns to solved this problem??
Is there a way to optimise further??
recursion
space complexity can be decreased further bu using sliding .Check on geeksforgeeks
You saved my butt big time on understanding this algorithm man! Good work on the tutorial!
Is this the Indian version of Ray William Johnson?
How? man How do you see the resemblance?
LMFAO!!!!
jokes on you ray william johnson is originally from india.
Fuck, i was about to comment that
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.
I dont get the up and going to the left part.
Let's say you have a basket that can hold 7 kg and you selected an item that is 4 kg weight which gives the value of 6 (best value). After selecting the weight of 4 kg, your basket can still hold 3 more kgs. For that if you go up and 4 steps to left (which means 7-4=3) , you will end up getting the best value that you had found for the remaining 3 kgs (which you had already calculated before coming to the place/row where you selected the 4 kg).
finally see it after 9 years
My exam is 2 days away and I'm still lurking on youtube for answers.. I'm so screwed
ヘンリーです no you are not alone fam
My Exam is today, and here I am :P
haha me too, my exam is 2 hours left
I am giving exam now , i am now in washroom watching this video
how did it go? @@jayjeetchakraborty7759
Tushar, your tutorials and explanations are awesome! Keep it coming mate!
didn't understood anything!!😟
+Tushar Roy oh sorry I forgot to mention
after I solved coin change problem by watching your video I understood both coin change and knapsack. thank you very much.
I need help for printing the selected elements.
please suggest me a condition for "while" or "for" loop.
+Sandesh Avhad
I haven't tested it but I believe you can do this
while(i>=0||j>=0)
then choose the maximum of the two print it and then alter the values of i and j accordingly
To the guys whose comments got deleted due to abuse.
Instead of abusing maker of the video try to understand the topic (if you really wish to learn something)
Use this which is the simplest. th-cam.com/video/sVAB0p58tlg/w-d-xo.html
That was a very clean and crisp explanation! Thanks Tushar
Making the most easier topic the most complicated one
Totally not satisfied
this video wasn't intended for toddlers.
i watched this 10 times to understand.. but i could not in any other videos. Keep going.
awesome sir!!
You my good sir, are an excellent instructor!
Accept my deepest gratitude for saving my ass as I couldn't make heads or tails of this particular algorithm until i stumbled upon your tutorial.
man, why are you in so much hurry...
it all went above my head...didn't get anything..
are londa
Maybe you're incompetent
try seeing the complete video and watch every iteration. I didnt understand in the starting but then when he came to the third row, that was the time things suddenly started becoming clear.
@@samacker77youtube If he knew it he will not be watching tutorial in youtube
You are wonderful Tushar! Thanks for the videos! They are very easy to understand.
Gautam Gambhir
the only video with rqd proper explanation for this problem
The best part is 9 is the winner😂😂😂 at 11:15
Deepak Bisht Bhai issi se pda h knapsack ?
Hunger games who's this
Deepak Bisht tere picche jo baith ta h shampy Singh Sabharwal😁
Hunger games 😂😂👌
waah dono topper yahin mil gye :P
Very nicely explained. Understood the algorithm very well. Thanks Tushar!
You're the best thank you
It was a nice discussion on 0-1 knapsack. I clearly understood all of it. Thank you for this .
You're a good teacher, but you need to slow down. English is my first language and you're going too fast.
...there's pause? I usually speed up lecture videos.
Martin Krauser
I did use pause. I still like to learn at a pace where I can actually hear what they're saying.
It's all practice. You should check out blind programmers, they listen to their code being read out, and they work at a similar speed to seeing programmers. Insane talking speeds.
Really clear explanation and step by step instruction - no obfuscation - thanks for the great video!
Did i m the only one who noticed the mistake at row 3 that should be 01145689
No. How can u get an total value of 8, when your capacity in that column is only 6. There are only two possible ways: put in weight 4+1 (value 6) or 3+1(value 5).
Or look at this approach: If you take weight 4 with value 5, you still have weight left, therefore you go one row up and go 4 columns to the left => 5+1 = value 6
You explain it way better than my prof does! Thank you.
you are teaching like we know everything and we are just rehearsing the topic from your tutorial.. dude its so bad..
vedant bhagwat he is teaching like a pro. if u don't understand simple algorithm do not jump on to dynamic programming . first get use to simple algorithm then go for dynamic programming.
This is the best explanation of the knapsack problem! Thank you very much.
most confusing explanation
Right
bro explanation was on point and the most practical
Excellent, cleared up my misconception about picking individual higher weight items from a set of items to get closest to target value.
this is the hardest way i have ever see... make it more easy......
Brother this is the simplest way...
you're ri8 Istiyak
This is standard DP solution and really simple and clear, you'd better use this kind of thought when you meet DP problem in the future.
it might help to watch it more than once...give it a day or 2 come back and watch it again...hopefully it makes more sense then
Why don't you accept you're just too dumb to understand this tutorial?
This is the best pace someone can explain algorithms! Thank you!!!
You should check out Joey'sTech for one of the best explanation of the 01 knapsack problem
@@joeystechpluscode Thank you Joey, I just checked, and your videos are really good too. I think you guys have different viewers though. I have already read and studied and understood these problems once in my life, and I just need to review all of them with a fast pace in a short time to get ready for an interview. Your videos are a bit slow for me. But I would suggest them to any friend who are looking to understand the problem and solution.
@@Andisheh65 Thank you !!
useless explanation very hard to understand
I was sure that I was going to fail on the quiz on Sunday. You gave me a little hope man. Thanks.
Great explanation of the 01 Knapsack dynamic programming algorithm. Super clear.
Amazing tutorial, you explained the process in a very understandable and complete way. Great job man.
Crystal clear explanation, So easy to understand.I must appreciate your effort.
Tushar je prije svega jedan veliki gospodin!