Table of Contents: (my bad if I'm loud, this video is old and the KZread 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.

@leozhang1340

5 жыл бұрын

Hey man, what's V sub i? from your max() function?

@fpv_am

4 жыл бұрын

Woooooooooooooooooooow, doode

@anshulabhinav13

4 жыл бұрын

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 !!

@BackToBackSWE

4 жыл бұрын

@@anshulabhinav13 yo

@BackToBackSWE

4 жыл бұрын

@@leozhang1340 The value of the i'th item

Someone give that man a medal

@BackToBackSWE

5 жыл бұрын

hahahaha, the comments I get keep getting funnier

@nitinpathak8763

5 жыл бұрын

Just came here to thank you again. It's because of your tutorials I got a job at Amazon 😎

@BackToBackSWE

4 жыл бұрын

@@nitinpathak8763 nice

@omi04

4 жыл бұрын

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

@jashanbansal2613

4 жыл бұрын

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

@BackToBackSWE

4 жыл бұрын

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!

@BackToBackSWE

4 жыл бұрын

thanks and thanks

Wow you're so brilliant. Thank you for slowing down this problem for me. I was so confused in class 😂

@BackToBackSWE

5 жыл бұрын

Tis' what we do

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.

I think the best channel related to coding. He explains everything in a really good way. Thanks a lot Benyam Ephrem.

@BackToBackSWE

3 жыл бұрын

thanks and thx

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.

@BackToBackSWE

4 жыл бұрын

thanks

I have seen very few people with this level of passion for teaching....Thank you sir for teaching so passionately!!!

@BackToBackSWE

3 жыл бұрын

sure lol

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.

@BackToBackSWE

4 жыл бұрын

yes

Went across the internet could not find a better taught tutorial than this, hats off man!

@BackToBackSWE

4 жыл бұрын

welcome to the show

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!

@BackToBackSWE

4 жыл бұрын

sure

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 love your passion, man. Not only great teaching, it's also fun to watch you!

@BackToBackSWE

3 жыл бұрын

yeah - I care lol

give this man a beer!

@BackToBackSWE

4 жыл бұрын

yes

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.

@BackToBackSWE

Жыл бұрын

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/

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.

@BackToBackSWE

3 жыл бұрын

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 :).

@BackToBackSWE

3 жыл бұрын

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!!!

@BackToBackSWE

4 жыл бұрын

nice

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

@BackToBackSWE

4 жыл бұрын

sure, you are welcome, go flourish in the world

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!

@BackToBackSWE

4 жыл бұрын

nice, thx

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 KZread. Keep doing the good work !!

@BackToBackSWE

4 жыл бұрын

ye

This is amazing, just wanted to say thanks. I've been struggling with understanding other explanations for a while now. This video really helped.

@BackToBackSWE

5 жыл бұрын

excellent

I've struggled with the knapsack problem for so long. I learned a lot from your video. Thank you!

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!!!!!!!

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.

@BackToBackSWE

3 жыл бұрын

welcome

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

@BackToBackSWE

5 жыл бұрын

hahahaha, this is one of the top comments on the channel

your energy is off the charts and this video was amazing. tysm

@BackToBackSWE

3 жыл бұрын

lmao my b old video - angry time in this beings life

You're the Sal Khan of programming interview concepts, my friend. Bless!

@BackToBackSWE

4 жыл бұрын

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.

The way of explanation of this guy is just awesome. I gone through few explanations but I found this best.

@BackToBackSWE

4 жыл бұрын

hello

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!

After multiple videos and almost giving up on it since a year, I finally understood 0/1 Knapsack.

@BackToBackSWE

3 жыл бұрын

great!

Amazing man! Especially how you dived deep into the logic of constructing this matrix. Thanks for this and all the other enriching videos!

@BackToBackSWE

4 жыл бұрын

thanks and sure

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

@BackToBackSWE

4 жыл бұрын

thx

I wish I could give this more than just one thumbs up, thank you for explaining this so clearly and concisely.

@BackToBackSWE

4 жыл бұрын

sure

Man you just made my day. Now I found what my motivation to study algorithms was missing. Great help!!!

The best explanation of the knapsack problem using DP that I got on the internet.

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.

@BackToBackSWE

5 жыл бұрын

AWESOME!! Tell me how it goes!! Man...this is literally why I do this. Thank you for commenting. Thank you.

@dephc0n1

5 жыл бұрын

@@BackToBackSWE got denied by the hiring committee but I wouldn't have made it to the 7th round without your help. Thank you bro

@BackToBackSWE

5 жыл бұрын

@@dephc0n1 sure...you were my first ever real comment on the channel...pretty cool :) I remember you.

Thanks to you I just gained your 1 months understanding in 20 mins! Really Grateful!!!

@BackToBackSWE

4 жыл бұрын

sure

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.

@BackToBackSWE

4 жыл бұрын

thanks and dang

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!

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

@BackToBackSWE

5 жыл бұрын

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

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!

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!

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!

@BackToBackSWE

4 жыл бұрын

thanks

After watching several videos it finally clicked at this one. Thank you!

@BackToBackSWE

4 жыл бұрын

nice

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

@BackToBackSWE

4 жыл бұрын

thanks

Really good. I didn't get what the algorithm did until you explained it. And you explained it extremely clearly.

Thanks a bunch for your energetic and clear explanation! I love it. Keep doing your good work!

@BackToBackSWE

4 жыл бұрын

sure thanks

I come back to this channel every time i have interviews. Youre awesome

@BackToBackSWE

2 жыл бұрын

Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

I enjoyed watching this video. Your energy made it more interesting and I finally understood this concept.

@BackToBackSWE

4 жыл бұрын

Nice - and great to hear

I dont know if you need reminder,but you hell helping a lot. Love your videos.

@BackToBackSWE

Жыл бұрын

Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=thwmas321 🎉

I lost counts of how many times you saved my ass in CS class... you deserve every medal in education

@BackToBackSWE

4 жыл бұрын

glad ur safe

@winter.bear.221

4 жыл бұрын

@@BackToBackSWE omg my idol replied xD

@BackToBackSWE

4 жыл бұрын

@@winter.bear.221 I reply to every comment i see

THAAAAAAK YOU!!! I WAS TRYING 5 DAYS TO UNDERSTAND THAT WITH NO RESULT!!

@BackToBackSWE

4 жыл бұрын

great

His explanations are so good and crystal clear.

@BackToBackSWE

3 жыл бұрын

thanks

I saved my (24*30*60 - 20) minutes to solve and understand this problem. Thanks Ben !!

@BackToBackSWE

4 жыл бұрын

nice hah

*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 love your enthusiasm in your videos, these videos are really really helpful, Thank you so much!

@BackToBackSWE

4 жыл бұрын

sure

Best explanation I've come across even with the weight/value confusion.

This is absolutely sick. I've never understood DP so better. I've got interviews lined up. Thanks!

@BackToBackSWE

4 жыл бұрын

ye

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.

@BackToBackSWE

4 жыл бұрын

yes

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 like how you explain. Clean and understandable English and lots of passion. Trully amazing!

@BackToBackSWE

4 жыл бұрын

thanks

Thanks for your enthusiam on this subject. I was dying looking at my books

Excellent video. The way you explain things is so natural. Thx a lot!

@BackToBackSWE

5 жыл бұрын

Yeah, thanks, I'm sorry, my initial videos were very low quality in audio and lighting. I hope it helped.

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

@BackToBackSWE

3 жыл бұрын

yeah i aint smart lol

Thank you - this really helped me clarify this in my head!

This guy is a gem 💎! Cos I see the genuine interest in knowledge sharing 👍🏻

@BackToBackSWE

4 жыл бұрын

thanks haha, im here

You should have at least a million subs, your content is just invaluable

@BackToBackSWE

4 жыл бұрын

thx

Dynamic programming is making sense now. All thanks 2 u. As usual u rock.

@BackToBackSWE

5 жыл бұрын

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!

@BackToBackSWE

2 жыл бұрын

Thanks buddy! To explore more content, head on to our subscription plan and avail 30% discount for some exclusive stuff b2bswe.co/3HhvIlV

Really solidified my understanding of the problem. Thanks for making this!

@BackToBackSWE

3 жыл бұрын

great and sure

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

@BackToBackSWE

5 жыл бұрын

Yeah, it is all about knowing how the subproblems decompose

@auto8ot644

5 жыл бұрын

Thanks bro! This is exactly what I had a problem understanding. Didn't click until I read that "items cannot be reused".

Your explanations are on point! This helped me so much, thank you :)

@BackToBackSWE

5 жыл бұрын

nice

Whoever even thought of this original solution approach for these style of questions is a genius

great video sir, u just saved my ass in my algo exam and now in my mini zinc problems. Respect from Moscow, Russia

This is the best content for this problem on KZread. 👌

@BackToBackSWE

4 жыл бұрын

thanks

I love all of your series on DP! Thank you!

@BackToBackSWE

5 жыл бұрын

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.

@christiansakai

5 жыл бұрын

@@BackToBackSWE Thank you! It's currently the best series on DP yet on KZread!

@BackToBackSWE

5 жыл бұрын

@@christiansakai 👀👀

every time he says it takes me a long time to grasp it. I think he just wants us to feel comfortable...

@BackToBackSWE

4 жыл бұрын

I mean yeah - things take me a while to grasp too

You are honestly AMAZING.

Thanks bro!! You're the best this was an amazing video I finally understand this

thank you so much for sharing this !! my search to understand this problem stops here.

@BackToBackSWE

7 ай бұрын

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

Subscribed! This dude explains in a very understandable way.

Thanks man, great work! Love the energy!!!

great explanation! thanks for such a good video on DP and the effort you put in to create each video.

@BackToBackSWE

4 жыл бұрын

thanks

love the passion and energy bro. Thanks so much

You're always giving the best solution. Thanks for the video!👍

Bro, this video is the best explanation I've ever seen and this totally change my view to solve dynamic programming!

@BackToBackSWE

Жыл бұрын

glad to know it helped

This is what my algorithms class is missing

@BackToBackSWE

4 жыл бұрын

yes

@sarahli2933

4 жыл бұрын

The idea behind the algorithm design should be the core of an algorithm course. The video managed to do that. Bravo!

Best Explanation of 0/1 Knapsack Problem!! Keep up the good work like this always!❤🙌

@BackToBackSWE

4 жыл бұрын

ye

@SR-we1vl

4 жыл бұрын

@@BackToBackSWE I want to work with you sir!

@BackToBackSWE

4 жыл бұрын

@@SR-we1vl We are looking for smart people, we are building a new platform with a code editor and may need technical writers. If you want to join you can contact us.

@SR-we1vl

4 жыл бұрын

@@BackToBackSWE Sure sir! Love to work with you😘😘❤️

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!

@BackToBackSWE

4 жыл бұрын

sure and thanks.

I don''t usually comment, but this video is too amazing not to say anything. Thank you! I finally understood this, and it was actually easier than I thought. You're awesome! Keep going.

@BackToBackSWE

4 жыл бұрын

ye

your channel is so underrated man! Amazing Explination

@BackToBackSWE

4 жыл бұрын

thx

Tuschar Roy knows thing, ur good at teaching those things. Man that passion, awesome.

@BackToBackSWE

5 жыл бұрын

Thanks.

The im feeling it edit is too real. I know exactly that feeling when you're in the flow of an explanation

@BackToBackSWE

4 жыл бұрын

hahaha

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.

@BackToBackSWE

5 жыл бұрын

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.