The 0/1 Knapsack Problem (Demystifying Dynamic Programming)
ฝัง
- เผยแพร่เมื่อ 20 ธ.ค. 2018
- 👉 NEW VIDEO & CODE: backtobackswe.com/platform/co... (free)
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
I was inspired to do this video after seeing that Tuschar Roy had covered this problem. He did a good job, but I feel it very necessary to stress what is really happening and what each cell REALLY means.
Dynamic programming is about subproblems, not remembering patterns to fill cells in with. I watched EVERY ONE of Tuschar Roy's videos and found myself MEMORIZING how to fill out the cells INSTEAD of really knowing what was going on.
I hope this video sheds light on what this problem is really trying to express.
I talked about the bottom up way to do things. Here is the code for that way of doing it: www.sanfoundry.com/java-progr...
You can also do it TOP DOWN with recursion where we investigate all expressions of the subproblems to find the optimal solution. The book Elements of Programming Interviews by Aziz Adnan has a very good version of this. The problem is 17.6 in that book.
++++++++++++++++++++++++++++++++++++++++++++++++++
Question: Write a program for the knapsack problem that selects a subset of items that has maximum value and satisfies the weight constraint. All items have integer weights and values. Return the value of the subset.
Can we do it greedily?
0/1 means you cannot split an item. If you could split an item, you could solve this greedily by sorting the item entries by value and then picking from greatest value to least. When you run out of space in your "sack", you'd split the last item and then you would have maximized weight vs value.
Brute Force: We could consider all subsets of items in a complete search and take on the cost of exponential time of 2^n (we will explain this in another video).
Greedy doesn't work, brute forcing won't make the cut, now what? What can we do now?
Dynamic Programming.
Notice that we can subproblem this.
Dynamic programming is not about stupid magic tables that you see people fill out, it is not about guessing. DP is about remembering the solutions to subproblems so that we can find the globally optimal solution. We just subproblemed this recursively.
This is where the table comes from. Each cell MEANS SOMETHING.
IT IS THE ANSWER TO THE QUESTION.
If we solve all the subproblems and remember all answers then we will find the globally optimal answer.
The subproblems are represented by what is called a recurrence equation.
Complexities
n = total items
m = max weight (max weight constraint)
Time: O(nm) (we will be solving this many subproblems)
Space: O(nm) (we will store the results of n*m subproblems)
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++
The 0/1 Knapsack problem is question 17.6 in the fantastic book Elements of Programming Interviews. - วิทยาศาสตร์และเทคโนโลยี
![[TH] VCT Pacific Stage 2 - Playoffs Day 3 // DRX vs GEN | PRX vs TLN](http://i.ytimg.com/vi/CWM1Q-2-o3M/mqdefault.jpg)
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 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!
I have seen very few people with this level of passion for teaching....Thank you sir for teaching so passionately!!!
sure lol
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 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.
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 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 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
give this man a beer!
yes
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.
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
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
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
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/
I love your passion, man. Not only great teaching, it's also fun to watch you!
yeah - I care lol
Went across the internet could not find a better taught tutorial than this, hats off man!
welcome to the show
your energy is off the charts and this video was amazing. tysm
lmao my b old video - angry time in this beings life
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
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'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
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
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.
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
After multiple videos and almost giving up on it since a year, I finally understood 0/1 Knapsack.
great!
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!!!!!!!
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
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 👏
*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 :)
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
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've struggled with the knapsack problem for so long. I learned a lot from your video. Thank you!
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
The way of explanation of this guy is just awesome. I gone through few explanations but I found this best.
hello
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
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
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!
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 enjoyed watching this video. Your energy made it more interesting and I finally understood this concept.
Nice - and great to hear
I love your enthusiasm in your videos, these videos are really really helpful, Thank you so much!
sure
Thanks a bunch for your energetic and clear explanation! I love it. Keep doing your good work!
sure thanks
Thanks to you I just gained your 1 months understanding in 20 mins! Really Grateful!!!
sure
I had to replay some parts of the video to really understand it but you gave us so much examples and decision makings that I could easily implement this in c++. Thanks for the really good quality content!
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!
I have never been this stressed watching a programming problem explained lmao
Man you just made my day. Now I found what my motivation to study algorithms was missing. Great help!!!
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
I wish I could give this more than just one thumbs up, thank you for explaining this so clearly and concisely.
sure
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
Excellent video. The way you explain things is so natural. Thx a lot!
Yeah, thanks, I'm sorry, my initial videos were very low quality in audio and lighting. I hope it helped.
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.
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
The best explanation of the knapsack problem using DP that I got on the internet.
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.
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 :)
After watching several videos it finally clicked at this one. Thank you!
nice
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 🎉
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!!!
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
Thanks man, great work! Love the energy!!!
Thank you - this really helped me clarify this in my head!
Your explanations are on point! This helped me so much, thank you :)
nice
This guy is a gem 💎! Cos I see the genuine interest in knowledge sharing 👍🏻
thanks haha, im here
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
great explanation! thanks for such a good video on DP and the effort you put in to create each video.
thanks
I like how you explain. Clean and understandable English and lots of passion. Trully amazing!
thanks
THAAAAAAK YOU!!!
I WAS TRYING 5 DAYS TO UNDERSTAND THAT WITH NO RESULT!!
great
Really good. I didn't get what the algorithm did until you explained it. And you explained it extremely clearly.
love the passion and energy bro. Thanks so much
I love all of your series on DP! Thank you!
No. Thank YOU for watching. Without viewers making meaning of this none sense I put out I am nothing.
Thank you for giving my work meaning, it means a lot.
@@BackToBackSWE Thank you! It's currently the best series on DP yet on TH-cam!
@@christiansakai 👀👀
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!
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!
Subscribed! This dude explains in a very understandable way.
Thanks bro!! You're the best this was an amazing video I finally understand this
His explanations are so good and crystal clear.
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
Really solidified my understanding of the problem. Thanks for making this!
great and sure
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
Your explanations are just awesome!!
good to hear
This helps me a looooot! Thank you so much!
Fantastic articulation and great clarity! Taking the time to go through the entirety of the procedure is a very useful and often necessary part of the teaching process that, sadly, too many people forget, so props for giving that extra effort! Only thing holding you back, in my honest opinion, is that you speak way too quickly. On TH-cam, people can pause and take a break (or re-run the video a few times), so it's not as dramatic as if this were a classroom, but too much energy and flow will detract from your otherwise remarkable clarity for people who have a harder time understanding the problem. Remember those people are trying to think while you talk, so they need as much breathing space as you can give them (without falling into the other extreme, of course). I would recommend experimenting with the way the video is cut. The montage is excellent, but it's clear it's arranged to create one massive, expertly flowing, high-speed delivery that may end up defeating itself by virtue of offering the info faster than it can be processed.
Another suggestion would be to avoid correcting mistakes made while recording with white-on-white script. by the time the viewer sees it, then reads it, you run the risk of losing them, in part due to the technical nature of said corrections that inevitably detract from their attention, and to the speed of the delivery.
And I'm not saying this to complain : this is by far one of the best explanations available on the net for this problem! There's clearly an immense amount of work both recording and post-prod that went into this, and you should be bloody proud of it! Thanks a lot for your work!
thanks
Superb passionate delivery! Thanks
Thanks for putting this together. This video is excellent
Best explanation I've come across even with the weight/value confusion.
Thanks for your enthusiam on this subject. I was dying looking at my books
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".
u explain fabulously.. keep making such videos.. they r really helpful to us
ye
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
@@winter.bear.221 I reply to every comment i see
This is the best content for this problem on TH-cam. 👌
thanks
Dynamic programming is making sense now. All thanks 2 u. As usual u rock.
thanks
just loved the way you explained it...thanks a lot!!
sure
Crystal Clear explanation!! Really Helpful
thanks
You are honestly AMAZING.
Great work! Easy to understand and follow.
thanks
You're always giving the best solution. Thanks for the video!👍
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.
This just makes DP make so much sense! Thanks!
nice
Great Job. Clear and well explained.
thanks
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
Outstanding work! :D
Please continue to share your passion with the world, sir.
thx and ok