Table of Contents: (my bad if I'm loud, this video is old and the TH-cam algo keeps feeding it) Problem Introduction 0:00 - 2:38 Walkthrough One Subproblem 2:38 - 4:38 The DP Table Introduction 4:38 - 6:12 The Recurrence Relation 6:12 - 8:30 What Each Cell Really Means 8:30 - 9:08 Solving The Dynamic Programming Table 9:08 - 16:46 Finding The Items That We Chose 16:46 - 18:32 Gearing Your Mind For Other DP Problems 18:32 - 19:07 Time & Space Complexities 19:07 - 19:45 Wrap Up 19:45 - 20:10 This is the 0/1 Knapsack Problem. The key is to see the subproblems. DP is just something that takes seeing a lot of problems to get a solid grasp of. I still do not have a full grasp of the subject myself.
Really love the passion u show for solving these problems....this is so hard to see these days...feels like u r in a zone or something when u r explaining....kudos & keep it up !! May u remain as excited !!
@@nitinpathak8763 Hey, I have an interview scheduled. I'm done with round 0 (coding test) up for round 1-4. I could really use some tips. Thanks in advance...:)
I just came across your channel and I would like to show my appreciation for what you do. Your energy and enthusiasm when explaining these problems is contagious! Super helpful for someone who is learning programming from scratch. Thank you for your hard work!
Every other TH-camr: "In this DP problem, just do this math, and the problem is solved." Back to Back SWE: Explains why we do every step. I've watched a lot of dynamic programming (DP) videos, but only your videos have given me a clear understanding of each step. Using the thought process from your videos, I have been able to successfully solve all DP problems with complete intuition.
im sooooo glad I've found your channel, this problem was giving me a HEADACHE yesterday, and you're the only one who explained it in such a brilliant way so far!!! i hope I also understand the asymptotic notations from you, they've given me a heart ache for the ENTIRE semester ughhh!!
I love how you explain things! You don't skip steps and at the same time have great banter as you progress through even simple steps. It allows me to follow along and eventually grasp how the solution needs to be approached. I'm very impressed. Well done!
I think, to approach this problem from DP table perspective is a little difficult intuitively. My approach is, just recursively solving sub problems like Climbing stairs or Egg Dropping. First define *base cases* *Case1* : if the weight capacity is 0, then we can’t choose any item. Hence the optimum value is 0; *Case2* : if the number of items is 0, then we can’t choose any item. Hence the optimum value is 0; *Other cases* *Case3* : if the weight of the Nth Item is greater than the max weight capacity, then, we have only one option, i.e. NOT choose that item, but to choose from remaining(N-1) items for the same weight capacity. *Case4* : if the weight of Nth item is equal to or lesser than max weight, then we have the 2 options. Either to choose the item or Not to choose. But the decision to be made is depending on whether we get max value by choosing Nth Item or not choosing the item but choosing from the remaining (N-1) items. i.e If we choose Nth item, then value1 = (value Of Nth Item) + (optimum Value from remaining N-1 items for the remaining weight). If we don’t choose Nth item, then value2 = (optimum Value from remaining N-1 items for the max weight) Now our optimum value is max(value1,value2); private static int optimumValueRecursively(int n, int maxWeight ){ //Base cases 1 and 2 if(maxWeight==0 || i==0){ return 0; }
i was stuck with this problem for way too long... none of them explained so deeply and simply.... u pointed out each and everything ..... brilliant man , just brilliant .... even geeksforgeeks could not help me .. thanks man
Not having the items in order by weight is a great touch 👌 Thanks for doing that. Intuitively, people would assume they have to which really doesn't change the result.
This is the probably the 4th or 5th explanation of the knapsack problem that I've watched in the past few days. THIS is one where I had the moment of epiphany where I said "OH... I get it." Thank you.
You are the best one I learn from him because you focus on the idea of the solution, not the solution itself and memorizing it. Thank you for your efforts.
Out of all the videos I watched, none explained why you go to the row above in the same column and why you go to the column left in the same row. Thank you for explaining this!!!
I must've watched 2 videos and read 3 articles about the Knapsack Problem, and still came to this video absolutely confused.....but this explanation was so clear that the Knapsack Problem & DP make sense to me now. Brilliant work explaining this solution 👏
Man... The amount of effort that you put in these videos is literally unmatchable, and that has made these difficult-to-grasp concepts very intuitive! A big thanks to you!
I love you energy and the enthusiasm you put in to make a person understand. It just really makes me wanna sit and listen. Thanks for videos like these :).
This is hands down the BEST explanation of this problem I have ever seen!!! I don't know if it's just me but generally I really struggle wrapping my head around the knapsack problem, I just never fully get i. This makes so much difference, thank you!!!
Hello there , On LeetCode there is a question - Target Sum -Find out how many ways to assign symbols ( - + ) to make sum of integers equal to target S. Can this be solved with the same approach as explained in this video ? Will you be able to share your thoughts or put a video for this ? Here is the problem .......You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
This is the best DP problem explanation video I've ever watched! I can say 90% of instructors in the universities couldn't do better than you bro. Salute! Hope you can continue to make awesome videos!
Happy Holidays! Really glad to help 🎉 Thank you for subscribing. Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/
The best thing I find about your videos is that you show the whole thought process of solving a problem. I must say you are a lot better than Tushar Roy ! In fact I think you are the best Computer Science teacher on TH-cam.
Man i was about to give an algorithm lesson to college trainees at office tomorrow and I was finding it difficult on how to clearly and concisely approach knapsack dp without overwhelming them with info and random code. This dry run of yours is fantastic. I think I will just go with how you explained it. This is just great.
Hey man, you are a great teacher, just wanted to let you know. Your enthusiasm is infectious, and I will definitely look at more of your material in the future.
at the last moment when he says that "it tooks him almost 1 month to undestand" it gives me more satisfaction than anything because still i am thinking that i missed something about this problem i saw almost 15 video still didnt get it properly
This is a decent explanation, taken as a whole. My main advice to you is this: focus on why this works. Each dynamic programming problem has CRITICAL OBSERVATIONS that sets up the recurrence. In the 0-1 knapsack problem, it's essentially these observations: 1) For any given item, we can either choose to include or exclude it from the knapsack. 2) For any given state of knapsack containing items already (call weight kw and value kv), when considering a new item with weight iw and value iv, we only need to decide if adding the item would result in a better knapsack. So we are comparing 2 values: the kv at kw-iw, and the value of not taking the item (optimal solution for current weight). In essence, all dynamic programming solutions boil down to these 2 steps. First, we have to be able to conceptualize an enumeration of the possible solution space. In this case, it's pretty straightforward: shall we take the item or not? 0-1 problems typically lead to a O(2^n) time complexity for the brute force solution, which you did a good job identifying in your video. In the second step, we have to realize that an optimal solution for the next item does not need to consider all previous items, ONLY THE SOLUTION for the previous item/weight remaining combo in the knapsack. This is NOT trivial, and this is the CRITICAL OBSERVATION that needs to be made for this problem. Really, for programming interviews, time constraints can be unfortunate because this critical observation is like solving a riddle. It either happens, or it doesn't. Having seen the problem before makes it easy, but there's no surefire way to make the observation for problems you haven't seen before. Of course practice helps, since almost all DP problems use some kind of n-dimensional matrix to hold intermediate solutions. Sometimes we can walk backwards from imagining a table of solutions and then simply prove the observation implied by the table. When you started drawing the item / weight remaining matrix, I immediately started thinking to myself, "Is it the case that, knowing the optimal solution for a given weight remaining / value combo, I can determine the optimal solution plus the next item without considering all previous items?" Having experience proving logical theorems can help with this step. Any good dynamic programming tutorial needs to focus on these two steps. Otherwise, it will be confusing the for the student.
Sorta...he is way more pure. I just want to build a large, honest, and effective business that makes people's lives better. He is on another level of purpose and vision. I'd hope to be there someday.
I am regretting now why can't I able to find your channel 1 year back. Your content is really amazing, and you make me learn DP in such an easy way, before today, I always feared from DP, but now it looks cool to face and try to solve the problem with DP.
after 12 seconds into the video I knew my hour long search for a REAL explanation was over... Thank you man, there should be more people like you in the field of computer science stuff...
Great video. The thing that took the longest time to click for me in this problem was in the case where the weight of the item was less than the current amount we are at. Was confused as to why we not only decrement column by weight, but ALSO decrement row by 1, until I realized that items cannot be reused. I was under the impression that we have infinite number of each item. Having only 1 of each item makes this make sense
Initially I assumed dynamic programming as a mind blender remembering all tabular approaches practicing a bit But...... This one video changed the perspection of dynamic programming, how can we apply this approach to all other problems. Thanks a lot from bottom of my heart Please I request you to make more videos on dynamic programming. One who is perfect in dynamic programming is a master of Data structures and algorithms You are the one
This is so superior to any other tutorial on this subject here. You explain it very well Sir, down to earth but not to the point where it's oversimplyfied. Richard Feynman would be proud.
Thanks a lot. One knowledge to solve many problems. Similar approach to solving problems like "Coin change", "Shopping", etc. I prefer using the recursive DP. I could come up with solution in few minutes. Thanks for helping me see a different way to think about the problems.
In my class I got the same but with also value constraint (target profit) and the table is filled with weights and the values are on the columns instead. Additionally, due to that difference, infinite value is used instead of 0, apart from the 1st column. But your explanation helped very much understanding the base algorithm. Amazing explanation, thank you!
Excellent tutorials! Way better than my university's lectures. If you're planning to invest into this channel, it is probably worth putting up some acoustic foam panels to block the room's reverb and help the sound quality.
Yeah, this was one of my first videos. Look at the most recent videos. I have a mic now. Oh...and...backtobackswe.com/im-sorry This is something I realize a viewer can't realize. I never realized this stuff until I started making videos...how quality slowly gets better as you work out the "bugs" and then you get stuck with the old videos... That's just the nature of things.
I was having way too much of a hard time before discovering this. You're definitely in the zone after 12:21, and so was I by that point, this is a great video!
great video, i think the only thing missing would be to show the code for the bottom up approach and follow it just like you did with the table. Keep up the great work
Great video dude! I would recommend to please also mention that, once we use an element in a knapsack, we don't use it again. And that is why when we use a weight, we subtract that weight from the current weight and add it to the weight in the row above it(because we should not use that weight again - meaning the value on the same row, when we subtract it) . And that is the subproblem we are trying to solve. It took me a while to get my head around that, I hope this would help someone who is having the same problem.
Correct me if I am wrong, but for the greedy approach (fractional weight allowed), we should sort them by value/weight ratio, and not just value, as you mentioned.
You're right man, that's what the greedy approach does. If I remember correctly, the greedy algorithm could have problems and might not reach the optimal value. There's a very good book which describes the KP formally: Knapsack Problems by Hans Kellerer. Very good book although is too mathematical from my point of view, but reading the specific KP section from the book and watching a great video like this and you're good to go for implementing the algorithm in your favourite programming language.
Happy Halloween 🎃 Thank you for your kind words, Reengineer! We'd love to offer you a 50% Off our exclusive lifetime membership just use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
I don't think 0-1 by definition means that you cannot split item, it means that you can either take an item or not, as opposed to more than 1 items could be taken for bounded knapsack or unbounded knapsack problem. Correct me if I am wrong. check wikipedia
Yeah, by default you can't use more than one item so that bound is set. Max 1 use per item. 0/1 sets the "middle bound" of sorts saying no splitting...so either use 0 of an item or 1 of an item.
Thank you so much for your explanation. I appreciate the passion you have for this topic, and the way you explain the reasoning behind the table you construct is so helpful!
I think that the question is "Which is the maximum sum that I can have for height h if I start with Item i?" The answer is maximum (sum for h - i.height) + i.value
I must say that you are a great great great teacher and we can sense how excited you are for helping us along the way! Thank you very much and I hope you will get super big because you deserved it!!!!!!!
Great explaination! Minor correction on the runtime though. The runtime isn't O(NM) but instead psuedo-polynomial because its exponential in the word size of the integer type. For example if the weight is a 32 bit int on one machine and 64 bit on another machine, this exponentially increases the complexity (but it's only due to the word size so it's not exponential but rather psuedo-polynomial).
i really love the way you teach. It's really inspiring. hope you have a lot of lesson like this i love it and look forward to see your other video soon
This is awesome. Thank you for the detailed explanation. I also used "Grokking Algorithms" to consolidate my knowledge, especially to understand the concept of why we're going up one level (You're on 4max but the item 2 is 3lb, so we have 1 lb spare, (equates to going back three steps and looking at the corresponding value for item 1). Brilliant explanation. You're my hero!
I just wanted to make a point clear that here it is a bounded knapsack...so we cannot use the weights in the same row again and again along the row for different weights of the bag..that the reason we go 1 row up when we go "w" weight back in a row...pls correct me if I am wrong..
Table of Contents: (my bad if I'm loud, this video is old and the TH-cam algo keeps feeding it)
Problem Introduction 0:00 - 2:38
Walkthrough One Subproblem 2:38 - 4:38
The DP Table Introduction 4:38 - 6:12
The Recurrence Relation 6:12 - 8:30
What Each Cell Really Means 8:30 - 9:08
Solving The Dynamic Programming Table 9:08 - 16:46
Finding The Items That We Chose 16:46 - 18:32
Gearing Your Mind For Other DP Problems 18:32 - 19:07
Time & Space Complexities 19:07 - 19:45
Wrap Up 19:45 - 20:10
This is the 0/1 Knapsack Problem. The key is to see the subproblems. DP is just something that takes seeing a lot of problems to get a solid grasp of. I still do not have a full grasp of the subject myself.
Hey man, what's V sub i? from your max() function?
Woooooooooooooooooooow, doode
Really love the passion u show for solving these problems....this is so hard to see these days...feels like u r in a zone or something when u r explaining....kudos & keep it up !!
May u remain as excited !!
@@anshulabhinav13 yo
@@leozhang1340 The value of the i'th item
Someone give that man a medal
hahahaha, the comments I get keep getting funnier
Just came here to thank you again. It's because of your tutorials I got a job at Amazon 😎
@@nitinpathak8763 nice
@@nitinpathak8763 Hey, I have an interview scheduled. I'm done with round 0 (coding test) up for round 1-4. I could really use some tips. Thanks in advance...:)
@@omi04 Hey Omkar!
How u applied for Amazon? Is it via referral or ...? Plz reply
I have seen very few people with this level of passion for teaching....Thank you sir for teaching so passionately!!!
sure lol
I think the best channel related to coding. He explains everything in a really good way.
Thanks a lot Benyam Ephrem.
thanks and thx
I love the way you teach. You break down the problem and at each point repeat what is happening so it stays in your head. Keep doing what you do.
I just came across your channel and I would like to show my appreciation for what you do. Your energy and enthusiasm when explaining these problems is contagious! Super helpful for someone who is learning programming from scratch. Thank you for your hard work!
Im telling you im scrolling through these knapsack videos on youtube, and yours by far are the easiest to understand. I wont need to scroll anymore
Every other TH-camr: "In this DP problem, just do this math, and the problem is solved."
Back to Back SWE: Explains why we do every step.
I've watched a lot of dynamic programming (DP) videos, but only your videos have given me a clear understanding of each step. Using the thought process from your videos, I have been able to successfully solve all DP problems with complete intuition.
im sooooo glad I've found your channel, this problem was giving me a HEADACHE yesterday, and you're the only one who explained it in such a brilliant way so far!!! i hope I also understand the asymptotic notations from you, they've given me a heart ache for the ENTIRE semester ughhh!!
nice
I love how you explain things! You don't skip steps and at the same time have great banter as you progress through even simple steps. It allows me to follow along and eventually grasp how the solution needs to be approached. I'm very impressed. Well done!
thanks and thanks
I think, to approach this problem from DP table perspective is a little difficult intuitively.
My approach is, just recursively solving sub problems like Climbing stairs or Egg Dropping.
First define *base cases*
*Case1* : if the weight capacity is 0, then we can’t choose any item. Hence the optimum value is 0;
*Case2* : if the number of items is 0, then we can’t choose any item. Hence the optimum value is 0;
*Other cases*
*Case3* : if the weight of the Nth Item is greater than the max weight capacity, then, we have only one option, i.e. NOT choose that item, but to choose from remaining(N-1) items for the same weight capacity.
*Case4* : if the weight of Nth item is equal to or lesser than max weight, then we have the 2 options.
Either to choose the item or Not to choose.
But the decision to be made is depending on whether we get max value by choosing Nth Item or not choosing the item but choosing from the remaining (N-1) items.
i.e
If we choose Nth item, then value1 = (value Of Nth Item) + (optimum Value from remaining N-1 items for the remaining weight).
If we don’t choose Nth item, then value2 = (optimum Value from remaining N-1 items for the max weight)
Now our optimum value is max(value1,value2);
private static int optimumValueRecursively(int n, int maxWeight ){
//Base cases 1 and 2
if(maxWeight==0 || i==0){
return 0;
}
//case 3
if(weights[n]>maxWeight){
return optimumValueRecursively2(n-1, maxWeight);
}
//case 4
int optimumValue =
Math.max((values[n]+optimumValueRecursively(n-1, maxWeight-weights[n])),
optimumValueRecursively(n-1, maxWeight));
return optimumValue;
}
There is no DP table involved in the above solution, DP table is useful when we consider memoization.
yes
i was stuck with this problem for way too long... none of them explained so deeply and simply.... u pointed out each and everything ..... brilliant man , just brilliant .... even geeksforgeeks could not help me .. thanks man
sure, you are welcome, go flourish in the world
I'm almost crying after watching so many videos of explaining this problem and still couldn't understand it.. until this one! Thank you so much!
sure
Not having the items in order by weight is a great touch 👌
Thanks for doing that. Intuitively, people would assume they have to which really doesn't change the result.
yes
This is the probably the 4th or 5th explanation of the knapsack problem that I've watched in the past few days. THIS is one where I had the moment of epiphany where I said "OH... I get it." Thank you.
great
Went across the internet could not find a better taught tutorial than this, hats off man!
welcome to the show
You are the best one I learn from him because you focus on the idea of the solution, not the solution itself and memorizing it. Thank you for your efforts.
thanks
Out of all the videos I watched, none explained why you go to the row above in the same column and why you go to the column left in the same row. Thank you for explaining this!!!
your explanations are much better than others teaching dp on youtube, not going to name names (I'm sure you know) and you deserve a medal
hahahaha, this is one of the top comments on the channel
I love your passion, man. Not only great teaching, it's also fun to watch you!
yeah - I care lol
I must've watched 2 videos and read 3 articles about the Knapsack Problem, and still came to this video absolutely confused.....but this explanation was so clear that the Knapsack Problem & DP make sense to me now. Brilliant work explaining this solution 👏
I've struggled with the knapsack problem for so long. I learned a lot from your video. Thank you!
Man... The amount of effort that you put in these videos is literally unmatchable, and that has made these difficult-to-grasp concepts very intuitive! A big thanks to you!
nice, thx
After multiple videos and almost giving up on it since a year, I finally understood 0/1 Knapsack.
great!
I love you energy and the enthusiasm you put in to make a person understand. It just really makes me wanna sit and listen. Thanks for videos like these :).
ye - good lol
This is hands down the BEST explanation of this problem I have ever seen!!! I don't know if it's just me but generally I really struggle wrapping my head around the knapsack problem, I just never fully get i. This makes so much difference, thank you!!!
nice
Hello there , On LeetCode there is a question - Target Sum -Find out how many ways to assign symbols ( - + ) to make sum of integers equal to target S. Can this be solved with the same approach as explained in this video ? Will you be able to share your thoughts or put a video for this ? Here is the problem .......You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
I'm not sure I've never done that problem and do not know
This is the best DP problem explanation video I've ever watched! I can say 90% of instructors in the universities couldn't do better than you bro. Salute! Hope you can continue to make awesome videos!
Wow you're so brilliant. Thank you for slowing down this problem for me. I was so confused in class 😂
Tis' what we do
I have seen maybe 20 videos on the knapsack problem, and this was the only one that made me understand it. Thank you so much.
Happy Holidays! Really glad to help 🎉 Thank you for subscribing. Do you know about the BacktoBackSWE 5 Day Free Mini Course? Check it out here - backtobackswe.com/
every time he says it takes me a long time to grasp it. I think he just wants us to feel comfortable...
I mean yeah - things take me a while to grasp too
The best thing I find about your videos is that you show the whole thought process of solving a problem. I must say you are a lot better than Tushar Roy ! In fact I think you are the best Computer Science teacher on TH-cam.
haha, nah Tuschar Roy is the og...the Don might I say.
And I'd agree with the last part :) Wish I had more time
Man i was about to give an algorithm lesson to college trainees at office tomorrow and I was finding it difficult on how to clearly and concisely approach knapsack dp without overwhelming them with info and random code. This dry run of yours is fantastic. I think I will just go with how you explained it. This is just great.
His explanations are so good and crystal clear.
thanks
Hey man, you are a great teacher, just wanted to let you know. Your enthusiasm is infectious, and I will definitely look at more of your material in the future.
give this man a beer!
yes
at the last moment when he says that "it tooks him almost 1 month to undestand" it gives me more satisfaction than anything because still i am thinking that i missed something about this problem i saw almost 15 video still didnt get it properly
yeah i aint smart lol
This is a decent explanation, taken as a whole. My main advice to you is this: focus on why this works. Each dynamic programming problem has CRITICAL OBSERVATIONS that sets up the recurrence. In the 0-1 knapsack problem, it's essentially these observations:
1) For any given item, we can either choose to include or exclude it from the knapsack.
2) For any given state of knapsack containing items already (call weight kw and value kv), when considering a new item with weight iw and value iv, we only need to decide if adding the item would result in a better knapsack. So we are comparing 2 values: the kv at kw-iw, and the value of not taking the item (optimal solution for current weight).
In essence, all dynamic programming solutions boil down to these 2 steps. First, we have to be able to conceptualize an enumeration of the possible solution space. In this case, it's pretty straightforward: shall we take the item or not? 0-1 problems typically lead to a O(2^n) time complexity for the brute force solution, which you did a good job identifying in your video.
In the second step, we have to realize that an optimal solution for the next item does not need to consider all previous items, ONLY THE SOLUTION for the previous item/weight remaining combo in the knapsack. This is NOT trivial, and this is the CRITICAL OBSERVATION that needs to be made for this problem. Really, for programming interviews, time constraints can be unfortunate because this critical observation is like solving a riddle. It either happens, or it doesn't. Having seen the problem before makes it easy, but there's no surefire way to make the observation for problems you haven't seen before.
Of course practice helps, since almost all DP problems use some kind of n-dimensional matrix to hold intermediate solutions. Sometimes we can walk backwards from imagining a table of solutions and then simply prove the observation implied by the table. When you started drawing the item / weight remaining matrix, I immediately started thinking to myself, "Is it the case that, knowing the optimal solution for a given weight remaining / value combo, I can determine the optimal solution plus the next item without considering all previous items?" Having experience proving logical theorems can help with this step.
Any good dynamic programming tutorial needs to focus on these two steps. Otherwise, it will be confusing the for the student.
The best explanation of the knapsack problem using DP that I got on the internet.
idk if you'll see this comment, but I read and watched a lot of videos about this problem, but yours was the most useful one. thank you so much!
The way of explanation of this guy is just awesome. I gone through few explanations but I found this best.
hello
You're the Sal Khan of programming interview concepts, my friend. Bless!
Sorta...he is way more pure. I just want to build a large, honest, and effective business that makes people's lives better. He is on another level of purpose and vision. I'd hope to be there someday.
I am regretting now why can't I able to find your channel 1 year back. Your content is really amazing, and you make me learn DP in such an easy way, before today, I always feared from DP, but now it looks cool to face and try to solve the problem with DP.
welcome
your energy is off the charts and this video was amazing. tysm
lmao my b old video - angry time in this beings life
after 12 seconds into the video I knew my hour long search for a REAL explanation was over... Thank you man, there should be more people like you in the field of computer science stuff...
thx
Really good. I didn't get what the algorithm did until you explained it. And you explained it extremely clearly.
Best explanation I've come across even with the weight/value confusion.
Great video. The thing that took the longest time to click for me in this problem was in the case where the weight of the item was less than the current amount we are at. Was confused as to why we not only decrement column by weight, but ALSO decrement row by 1, until I realized that items cannot be reused. I was under the impression that we have infinite number of each item. Having only 1 of each item makes this make sense
Yeah, it is all about knowing how the subproblems decompose
Thanks bro! This is exactly what I had a problem understanding. Didn't click until I read that "items cannot be reused".
Initially I assumed dynamic programming as a mind blender remembering all tabular approaches practicing a bit
But......
This one video changed the perspection of dynamic programming, how can we apply this approach to all other problems.
Thanks a lot from bottom of my heart
Please I request you to make more videos on dynamic programming.
One who is perfect in dynamic programming is a master of Data structures and algorithms
You are the one
nice
This is so superior to any other tutorial on this subject here. You explain it very well Sir, down to earth but not to the point where it's oversimplyfied. Richard Feynman would be proud.
thanks and dang
Thanks a lot.
One knowledge to solve many problems.
Similar approach to solving problems like "Coin change", "Shopping", etc.
I prefer using the recursive DP. I could come up with solution in few minutes.
Thanks for helping me see a different way to think about the problems.
great video sir, u just saved my ass in my algo exam and now in my mini zinc problems. Respect from Moscow, Russia
*It will take a month to grasp this problem*
Me: *Watching it one night before my exam*
Though, I got the idea man! Thank you :)
Thanks to you I just gained your 1 months understanding in 20 mins! Really Grateful!!!
sure
Thank you for this! I have a b2b phone interview with Google in 3 weeks so I will be checking out most of your videos.
AWESOME!! Tell me how it goes!! Man...this is literally why I do this. Thank you for commenting. Thank you.
@@BackToBackSWE got denied by the hiring committee but I wouldn't have made it to the 7th round without your help. Thank you bro
@@dephc0n1 sure...you were my first ever real comment on the channel...pretty cool :) I remember you.
I like how you explain. Clean and understandable English and lots of passion. Trully amazing!
thanks
In my class I got the same but with also value constraint (target profit) and the table is filled with weights and the values are on the columns instead. Additionally, due to that difference, infinite value is used instead of 0, apart from the 1st column. But your explanation helped very much understanding the base algorithm. Amazing explanation, thank you!
Thanks buddy! To explore more content, head on to our subscription plan and avail 30% discount for some exclusive stuff b2bswe.co/3HhvIlV
THAAAAAAK YOU!!!
I WAS TRYING 5 DAYS TO UNDERSTAND THAT WITH NO RESULT!!
great
I have never been this stressed watching a programming problem explained lmao
Whoever even thought of this original solution approach for these style of questions is a genius
I dont know if you need reminder,but you hell helping a lot.
Love your videos.
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=thwmas321 🎉
Excellent tutorials! Way better than my university's lectures. If you're planning to invest into this channel, it is probably worth putting up some acoustic foam panels to block the room's reverb and help the sound quality.
Yeah, this was one of my first videos. Look at the most recent videos. I have a mic now. Oh...and...backtobackswe.com/im-sorry
This is something I realize a viewer can't realize. I never realized this stuff until I started making videos...how quality slowly gets better as you work out the "bugs" and then you get stuck with the old videos...
That's just the nature of things.
Give this man a raise!
I could've used one when this video was made....way back when...no one was watching. Then the internet picks things up and runs with them..over time
I saved my (24*30*60 - 20) minutes to solve and understand this problem.
Thanks Ben !!
nice hah
I wish I could give this more than just one thumbs up, thank you for explaining this so clearly and concisely.
sure
This is way better than those monotone videos that seem like they're trying to put you to sleep.
I lost counts of how many times you saved my ass in CS class... you deserve every medal in education
glad ur safe
@@BackToBackSWE omg my idol replied xD
@@holssi.e I reply to every comment i see
I was having way too much of a hard time before discovering this. You're definitely in the zone after 12:21, and so was I by that point, this is a great video!
This is what my algorithms class is missing
yes
The idea behind the algorithm design should be the core of an algorithm course. The video managed to do that. Bravo!
Thanks for your enthusiam on this subject. I was dying looking at my books
great video, i think the only thing missing would be to show the code for the bottom up approach and follow it just like you did with the table. Keep up the great work
Man you just made my day. Now I found what my motivation to study algorithms was missing. Great help!!!
I enjoyed watching this video. Your energy made it more interesting and I finally understood this concept.
Nice - and great to hear
Great video dude! I would recommend to please also mention that, once we use an element in a knapsack, we don't use it again. And that is why when we use a weight, we subtract that weight from the current weight and add it to the weight in the row above it(because we should not use that weight again - meaning the value on the same row, when we subtract it) . And that is the subproblem we are trying to solve. It took me a while to get my head around that, I hope this would help someone who is having the same problem.
yeah, this was an early video, was still learning how to teach and put a lesson plan together
@@BackToBackSWE Love your videos man, keep making them!
@@Percussion0104 ok
I come back to this channel every time i have interviews. Youre awesome
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
Correct me if I am wrong, but for the greedy approach (fractional weight allowed), we should sort them by value/weight ratio, and not just value, as you mentioned.
I am honestly not sure, I'd need to think further on this
You're right man, that's what the greedy approach does. If I remember correctly, the greedy algorithm could have problems and might not reach the optimal value.
There's a very good book which describes the KP formally: Knapsack Problems by Hans Kellerer. Very good book although is too mathematical from my point of view, but reading the specific KP section from the book and watching a great video like this and you're good to go for implementing the algorithm in your favourite programming language.
@@AlejandroRodriguez-qy3gh Dang, someone wrote a whole book on Knapsack Problems. Fascinating.
thank you so much for sharing this !! my search to understand this problem stops here.
Happy Halloween 🎃 Thank you for your kind words, Reengineer! We'd love to offer you a 50% Off our exclusive lifetime membership just use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
Bro, this video is the best explanation I've ever seen and this totally change my view to solve dynamic programming!
glad to know it helped
Amazing man! Especially how you dived deep into the logic of constructing this matrix. Thanks for this and all the other enriching videos!
thanks and sure
You should have at least a million subs, your content is just invaluable
thx
This is amazing, just wanted to say thanks. I've been struggling with understanding other explanations for a while now. This video really helped.
excellent
I don't think 0-1 by definition means that you cannot split item, it means that you can either take an item or not, as opposed to more than 1 items could be taken for bounded knapsack or unbounded knapsack problem. Correct me if I am wrong. check wikipedia
Yeah, by default you can't use more than one item so that bound is set. Max 1 use per item. 0/1 sets the "middle bound" of sorts saying no splitting...so either use 0 of an item or 1 of an item.
After watching several videos it finally clicked at this one. Thank you!
nice
This is absolutely sick. I've never understood DP so better. I've got interviews lined up. Thanks!
ye
This is the best content for this problem on TH-cam. 👌
thanks
Your videos rock man!! By far the clearer explanation of the Knapsack problem I have found in TH-cam. Keep doing the good work !!
ye
Thank you so much for your explanation. I appreciate the passion you have for this topic, and the way you explain the reasoning behind the table you construct is so helpful!
thanks
This guy is a gem 💎! Cos I see the genuine interest in knowledge sharing 👍🏻
thanks haha, im here
I think that the question is "Which is the maximum sum that I can have for height h if I start with Item i?"
The answer is maximum (sum for h - i.height) + i.value
What do you mean
THANNNNK YYou, you are the best algo teacher in the world
u explain fabulously.. keep making such videos.. they r really helpful to us
ye
I must say that you are a great great great teacher and we can sense how excited you are for helping us along the way! Thank you very much and I hope you will get super big because you deserved it!!!!!!!
Did anyone else have to watch this 3+ times for it to finally click?
Great explaination! Minor correction on the runtime though. The runtime isn't O(NM) but instead psuedo-polynomial because its exponential in the word size of the integer type. For example if the weight is a 32 bit int on one machine and 64 bit on another machine, this exponentially increases the complexity (but it's only due to the word size so it's not exponential but rather psuedo-polynomial).
i really love the way you teach. It's really inspiring. hope you have a lot of lesson like this i love it and look forward to see your other video soon
thanks
This is awesome. Thank you for the detailed explanation. I also used "Grokking Algorithms" to consolidate my knowledge, especially to understand the concept of why we're going up one level (You're on 4max but the item 2 is 3lb, so we have 1 lb spare, (equates to going back three steps and looking at the corresponding value for item 1). Brilliant explanation. You're my hero!
sure and thanks.
I just wanted to make a point clear that here it is a bounded knapsack...so we cannot use the weights in the same row again and again along the row for different weights of the bag..that the reason we go 1 row up when we go "w" weight back in a row...pls correct me if I am wrong..
yes, bounded
you can't imagine how much you helped me with your comment
Dynamic programming is making sense now. All thanks 2 u. As usual u rock.
thanks
Carefully, he is a hero!
hey
Really solidified my understanding of the problem. Thanks for making this!
great and sure