4.5 0/1 Knapsack - Two Methods - Dynamic Programming

[@akashsaxena2590]

i have not enough words to thank you.I had spine injury 2 years ago.So i am in wheelchair .With your help i have completed my degree. Really thank you sir. God bless you sir

[@yashdeepsingh1519]

lmao

[@cityisbetter]

@@yashdeepsingh1519 dude wtf 😂, why would u "lmao" this comment

[@its_a_big_world]

i hope you're better now.

[@fayezchamp9365]

Meaning of imao?​@@cityisbetter

[@cityisbetter]

@@fayezchamp9365 its L M A O not i, Laughing My Ass Off

[@gameboyatron1405]

Besides actually learning what I need to know, the best part about these videos is how nice and respectful everyone is

[@Forexx_boy]

Pasd hua kya😂

[@giannismaris13]

this man deserves a nobel or something. You are Ω(2^n) times better than my teacher!

[@muhammadusama5329]

hey, No teacher is better or worse. A teacher is a teacher and we have to respect every teacher around us. If you feel your teacher is not suitable for your mindset then change your path. No offense. Thanks.

[@sushantatimalsina9064]

@@muhammadusama5329 oh yeah your vision matters

[@sircosm]

@@muhammadusama5329 Very well said! All teachers deserve respect for what they do. There will always be some exceptions but even they should be respected for their passion and dedication towards this noble profession.

[@PureAsbestos]

@@muhammadusama5329 You clearly haven't had a class with a professor who teaches so poorly that more than half the students fail or drop out. There is such a thing as bad teaching.

[@tuskoub]

@@muhammadusama5329Counterexample: My professor falsely accuses students, ruins their lives with the accusation, blocks students from receiving tutoring or seeking help, has driven other professors away, and gloats about his high (nearly 70%) fail-rate. His algorithms assignments have nothing to do with what he teaches. There are no other options at this school and you can't transfer the class in. My teacher is absolutely the worst, ever.

[@MuffinLucas]

A simple white board and you blow most teachers out of the water. You are a VERY gifted teacher and I thank you!

[@smrjt9102]

SET method for solving 0/1 Knapsack starts at 19:26. And for Tabular method watch the lecture from the beginning. Thanks

[@rawnakfreak3539]

🤣 thanks

[@aarushitiwari4787]

Hey can you tell me that while we eliminate an ordered pair using dominance rule...so for applying that rule our ordered pairs should be arranfed in ascending order of profits right??

[@adarshsharma7229]

yes profits should be in ascending order @@aarushitiwari4787

[@adityaranjansahoo6261]

@@aarushitiwari4787 arranging the weights in ascending is the key here...because then we always check which prev weight to include or not

[@saitejasherla1551]

Amazing thing is , you don't need any institute but student's like us need you most sir 🙏🏻 For your teaching experience and explanation take a bow👏🙌💯

[@adamberry7536]

Watching your videos is when it really clicked for me that I need to drop the just-show-me-the-code-already mentality. Interviewers are more interested in this level of understanding than regurgitating flawless code on a whiteboard. If you take the time to watch videos like this you can write the code yourself because you really understand the underlying algorithm.

[@samudragupta719]

While others were struggling I just rocked in VIVA ! Showed full iteration. Thanks a ton Sir. Looking forward more from your Pandora's box. Take my humble regards 🙏

[@arkasingha6111]

Bro what do u study???

[@rapahel3717]

@@arkasingha6111 DAA or Design and Analysis of Organisation

[@fathimashahana9594]

Hjjjkjlĺo9

[@pkyadav6230]

@@fathimashahana9594 wt f babe

[@Aspect_GT]

@@pkyadav6230 nice go say it to your mom also

[@vivek__pandey]

your way of explaining is best among all videos.

[@vbvgtm]

Vivek Pandey achcha Bhai pandey😂😂 bilkul shi kaha

[@vivek__pandey]

Exam kesa gya bro , mera to first class gya...

[@CreatingUtopia]

agree

[@BackToBackSWE]

nah fam, check me out :) I cover this topic

[@nagamanikilari2996]

@@BackToBackSWE you explained string edition so well

[@-_RonyMir]

sir ,whenever i watch you explaining a topic one word pops up in my head "Learning sometimes seems Beautiful! and this is the way we should learn something".

[@meowzerilla]

13 words hai bhaisaab

[@Hayleeyyo]

Sir you saved my life, I’m from university of Toronto, computer science specialist, I have adhd and always fell asleep in class, I found it’s hard to follow with my professor, but your videos made the topic understandable and interesting !!

[@AkshatSinghania]

lmao , university of toronto is awesome , good luck with classes

[@gamerboy-su1uq]

So you have Schizophrenia as well?

[@ConverttoHinduism]

University doesn't matter, knowledge matter. People who don't get seats here in India go to Toronto University

[@MK-zf6or]

@@ConverttoHinduism indians love to go to canada lol, UofT is far superior than anything in India we see indians go to canada for education but never a canadian who went to india 😂

[@debdeepsanyal9030]

@@ConverttoHinduism do you even know how good university of toronto is. you don't. hence, don't speak.

[@haiderwaseem8355]

I tried to learn it from people but salute to this guy. He's Amazing!!! Thank you so much.

[@divijjain4674]

Remember to always write the weight in ascending order on the left of the table.

[@jay-rathod-01]

bro did you watch the video.

[@haidershahid371]

@@jay-rathod-01 He is not wrong

[@theundescribable1643]

i dont think it is necessary as by the end all of the objects are considered and you would have filled the cells with maximum profit

[@liammeck1379]

Just for future readers: the order of the items does not matter; no need to sort them. ``` import random m = 8 p = 1, 2, 5, 6 w = 2, 3, 4, 5 items = list(zip(p, w)) random.shuffle(items) results = [0] * (m + 1) for item_profit, item_weight in items: for target_weight in range(m, item_weight - 1, -1): results[target_weight] = max(results[target_weight], results[target_weight - item_weight] + item_profit) print(results) ```

[@-BONDLAMADHURI]

​@@theundescribable1643aq1

[@dinushachathuranga7657]

You are born to teach complex concepts in a simple way. Bunch of thanks sir❤❤💫

[@shuaib3788]

This dude is a legend or what ??? ! His calmness , calms my soul! .,.. *Cries* !! Keep it up Bari Bhai

[@priscillabenedetti4182]

This is the clearest explanation of the knapsack problem I've ever found online, thank you sir!

[@sanemind5712]

Well I have my algorithm exam tomorrow and honestly I don't like to read algo .. i was depressed that I might fail on my exam but then I found your channel and started learning ... And i'm quiet sure that I'm not gonna fail atleast ... Your videos really helped me a lot .. thank you so much sir ... Thanks a lot

[@UpdateWithAstro]

Best channel on KZbin for DAA Stop wasting time on finding others channel just follow this channel

[@nuwantattygalle5645]

and this udemy course is also super nice

[@vipulahuja2044]

Sir, I have never studied before the set method of 0/1 knapsack, after watching this video, i got to know about the set method which is very easy method, Thank you so much Sir

[@subhasmitajena1726]

Not from computer science background. This video is everything I needed. Thank you from the bottom of my heart.❤

[@rishisingh1296]

Why to worry when you have Abdul Bari

[@dossexplores]

Dei avanthada periya velaya pathutu poitan 😂😂

[@vishalrajal]

​@@dossexploresyean enna achu

[@sharath8309]

​@@dossexploresExam thapa agidutcha bro

[@rahmatsheikh2909]

No need to magaj Mari when you have Abdul Bari

[@sharath8309]

​@@vishalrajalunaku edhathu thapa aghidutcha bro

[@hjklmn9526]

110% marks to you sir.. This is a very complicated problem to understand. But after going through this video and actually drawing it in notebook i found it actually very easy..

[@shubhamdalvi9347]

Get this man a shield of subscribers! U are saving ur time ...for understanding these problems. Keep working and THANKS IS ADVANCE FOR FUTURE VIDEOS.

[@haidershahid371]

Amazing sir. I simply love it when you release an "Acha" During your lecture

[@hmm7458]

haha.. can't hold his Indian back for long

[@ritikraj.18]

Words are not enough to Thank you Sir! After going through a lot of videos, finally i found something which has cleared all my doubts regarding this problem. Thankyou 🙏🙏

[@TheyHurry]

You are probably one of the best instructors I've ever come across

[@engineerhiteshahuja]

I wish we had such great material during our college days. Huge thanks to you!! Keep rocking.

[@israelamamba9524]

I tried several tutorial, but this is the best and easiest to understand. I especially was looking for how the formula is used to derived the values in the table and this tutorial explains it as well. Thanks a lot

[@gourabchanda6427]

Best approach to solve any dp: 1. Learn to develop recursive logic from scratch. (TC is worst, you might end up with TLE) 2. Memoize the same recursive logic. (optimize TC but end up using extra space. SC is probably worse now) 3. Learn the art of transforming recursive logic to tabular. (you end up saving call stacks) 4. Optimize the space complexity as well. (now you have optimized space as well) PS: thank you sir, if you weren't there, probably many wouldn't have tried in the first place.

[@alexwhitewood6480]

Love the explanation! Can you elaborate what is meant by TC, TLE and SC?

[@gourabchanda6427]

@@alexwhitewood6480 TC : Time complexity TLE: Time limit Exceeded SC: Space complexity

[@subhalakshmithulasidas5699]

Thank you so much sir!!! I passed my DAA exam only with the help of your videos!! Sincere thanks!

[@gabrip7]

Even if I'm not using all of it now I bought both courses on udemy, because you algorith classes are helping me SO much with my Undergraduate thesis thank you

[@_Ojasmahajan]

Sir your method of teaching is absolutely phenomenal. would have never understood complex topics in DAA without your videos

[@bhuvneshmahajan6573]

It was easy to understand. I'm grateful to teachers like you for your great way of explaining concepts of C.S.E.

[@Sanakhan-ff2jd]

teaching is an art .... after wasting 24 hours to understate a lecture of same topic by some crazy optimization expert from very reputed university of west.... i finally, or would say i "Luckily" found this video, thank you for making it so simple ...

[@amitkumarchoubey2003]

गुरू ब्रह्मा गुरू विष्णु, गुरु देवो महेश्वरा गुरु साक्षात परब्रह्म, तस्मै श्री गुरुवे नमः 🙏🚩🚩🙏 इम्तिहान में सर्वदा अवल व बेहतर अंक आए 🙏🙏🚩🚩🛕🛕💐💐🪔🪔🌞🌞😊😊🕉️🕉️🕉️🛕🛕🚩🚩🙏🙏🌹🌹🌷🌷⛳⛳😃😃🇮🇳🇮🇳👏👏🦚🦚

[@amitkumarchoubey2003]

Great Gurudev Ji 🙏🙏🌹🌹🙏🙏⚽⚽🤗🤗💖💖💯💯🇮🇳🇮🇳⛳⛳🌹🌹🚩🚩🕉️🕉️🛕🛕🌞🌞🌸🌸📚📚🌺🌺🎈🎈🎯🎯💓💓✅✅💯💯🇮🇳🇮🇳🙏🙏

[@joyseekerarpit]

Its looking very easy to me now, today in class I wasn't able to understand it so I looked up for the problem on youtube and I met a genius. Thank you

[@AdamWhitakerWilson]

Saving my life just in time for finals! Thank You!

[@obliteratedcisco4709]

wait u dont think he is ugly tho that was slightly off-putting lol 😅

[@sumant9120]

Breakdown of the formula: ⭐V: DP table which stores values of subproblems ⭐V[i, w]: Maximum profit by considering the first 'i' elements in a bag of weight 'w' ⭐V[i-1, w]: Case when the current object is not included(~0) and the bag with current weight 'w' must be filled with the maximum profit possible (stored at 'i-1') ⭐V[i-1, w-w[i]] + p[i]: Case when the current object is included(~1) and the remaining part of the bag 'w-w[i]' must be filled with the maximum profit possible (stored at 'i-1') (~ Hence the name 0/1 knapsack problem)

[@varun6480]

My brain got damaged

[@swarnaislam8528]

Thnx

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@anshgoel2607]

@@jaideepsingh7955 In house robber we calculate Profit/weight where as in 0/1 Knapsack we can't divide the objects thus we store the profit value..

[@panchalmahidilip9415]

Brain left

[@madhavgupta3976]

Your method is the easiest, which explains the two method. It makes the algorithm easy to understand. Thanks a lot sir.

[@53_ananyayadav73]

Truly sir, watch many 0/1 knapsack video, got too puzzeled, how to solve this tabulation, readings article for the same, but gets on the sport clearation here, thank u so much sir for sharing ur vast knowledge with the students like us

[@Youthstrugglebyshreya]

The second method was much easier... N i watched your other videos as well ... Really useful for my DAA exam preparation... properly explained all steps

[@brockobama257]

but its 2^n bro

[@sagarmistry6210]

There teachers are freely available on KZbin, whereas after paying lacs of rupees, we don't get such tutors in our colleges. This is true Digital India.

[@audreygoveas1239]

You're the best! You teach in such a way that we understand the concept entirely!

[@Axayubale]

You are not teacher you are god of computer science...hats off u sir

[@KingBobXVI]

Well explained and easy to understand - though there's a mistake I think at around 18:20 where you say to subtract the profit of the item to get what to search for in the previous row, but you should be subtracting the weight of the chosen item from the weight of the bag (8-5 = 3) to get the column of the previous row(s) to check for inclusion. This more intuitively makes sense to me as well, because you're ultimately just splitting the problem into smaller sub-problems - you've chosen the 4th item to include in the bag, and now you're looking at the previous row to determine what was the optimal solution for a bag of size 3, now that the _remaining_ weight you have to work with is 3. The additional profit you can add to a bag of size 3 is 2, so the rest of the explanation is the same. With that correction, I think the explanation is good enough as well that it's really easy to expand from a 0/1 solution to a 0/n solution (including as many of each item as you want).

[@fardinalam7290]

i think 8-6 =2 used because max profit for bag is 8 and 8 is located in 5th row which is wight 5 which selected for including in bag. and then maximum profit is 8 5th row profit is 6 then 8-6 = 2 , and now we have to search in which row profit 2 is located which is 3rd row of weight 3 so in bag{wi 3,5} selected with max profit 8. please correct me if i am wrong

[@KingBobXVI]

@@fardinalam7290 - I think that's incorrect, you want to subtract weight because that's the bounded variable. You want the most profit per unit of weight, and there's no limit to potential profit. Conceptually, you're solving sub-problems until you reach the final query. If ƒ(8) says the optimal item to take is weight 5, then you add its value, and query with the remaining bag capacity for ƒ(3), repeat until done. You don't want to take off the price, because that's a different unit than your input variable of weight. Note: I haven't watched this in a while, so I'd have to review it to be sure. I recommend solving the problem on paper, it helps give a better understanding of how it works. Especially if you explain it to someone else. However, that gave me an idea - it could be interesting to add another bound for this to limit the price as well - rather than taking items worth as much as possible like some kind of heist, maybe you're instead buying so you want to keep the price low, haha.

[@harshitha4886]

Sir I have seen videos on how to fill the table in knapsack problem. But u have explained why we are filling a particular value in that way only. You are an amazing teacher . Thankyou so much Sir.

[@star77670]

Please reply what if m =30 How many columns should we take ??

[@mayurisanjaynikam202]

Seriously sir just because of you i feel relax ....i was just in depression of this type of examples cause i thought it takes lot of time ...but you proved me wrong .. thanking you sir

[@neogen23]

Never heard of your channel before, unfortunately. Just watched this video, and I don't need a second one to understand the problem. I guess that's as good a compliment as it gets

[@michelletan4249]

the best professor I ever had, professor Abdul Bari is amazing!

[@naveen4421]

Yup

[@ahmetlacin5748]

Mr Bari: Thank you so much. I was struggling to understand this problem and was not able to find an explanation as clear as this. Thank you so much again.

[@michaelkochka7668]

Love your videos! Just purchased your data structures course on Udemy because you explain things so well.

[@praveenakushwaha9221]

Sir, you cleared all confusions. Thanks a ton, You made it very easy to understand.

[@tauhidhasan9073]

Thank you sir, as you know its soo hard to remember the rules of AI maths for a long time. Exam is knocking on the door and you just saved a lot of us. Thanks a lot sir, you r great

[@md.nayeemhasanadil5938]

without you sir what would we do. You are the savior of computer engineering students

[@siddharthasriramvinjam167]

Seriously I owe you a lot as your way of explaining the concept is very helpful to below average students like me. Thank you so much Sir.

[@harish_madhan]

Dear Sir, Only the Genius mind can give these kind of explanation and make it looks simple. You are genius sir. Thanks a lot for sharing tremendous knowledge to us. According to me, for this moment. I can see the God in you that shows a way for my well being. You are the GOD ❤

[@mohammadyousef2812]

i pray Allah award you jannah for this explanation. Thank you so much.

[@nohaelhaddad4425]

AMEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEN

[@abuzaformohammedaman9205]

Right bro

[@Jumabuoy]

For the first time I'm forced to comment on these educational videos cause, I mean you the BEST LECTURER,,, You deserve a nobel or smth really...

[@sankararaoijjada4786]

I will be graduated by watching these videos only rather than listening my faculty lectures ❤

[@abuzaformohammedaman9205]

Same bro

[@AnnaSidor-w8c]

you are heaven sent - i got it after watching the first 10 minutes, i love your videos, the are super helpful

[@majidzarinkolah]

In w - w[i] expression, the first w refers to the capacity and the second w refers to the weights list. It would be better to rename one of them. for example declaring the capacity as c. totally the way of teaching is delicious and the teacher has so much of charisma. Thanks to him!

[@starsky9832]

Thank you sir, this is the clearest explanation in this topic, the others just blindly apply formula without explanation.

[@jhguygih]

I've watched 95% of the alghoritms playlist. I sure own this teacher some money, is to much work done. How do we support him?

[@rishabmallick6]

He has a patreon link in the description of this video

[@bhawna1997]

Big salute to sir for explaining it so well! Best explanation of tabulation method of knapsack till now on KZbin!

[@AbdulMalik999]

Thank you Mr. Abdul Bari. I am grateful for your lectures.

[@harshitm6403]

Really Helpful videos... My go-to videos for my entire Data Structures and Algorithms course in college. Even now it is helping me prepare for competitive coding.

[@KevrenBey]

king of the algorithms ...thanks from Turkey..

[@cynthiachristelle]

thank you so much!!! i'll make sure I mention your name during my degree acceptance speech

[@Bobby-mf6fw]

You make the subject easiest. We are thankful to you sir.

[@sogatturlakshmi1245]

Sir, when you excellently explained the logic for three rows, then for fourth row I really don't care about what the formula is. Because I understood the concept well. This is the actual way of explaining things to students. They should not be told the formula first. The concept should be explained first. Then the formula should be told. Then students can easily relate both of them together 🙂. Thank you so much for this video sir.

[@kartikpeddinti487]

thanks a Ton for the set method.Great explanation sir.Your video order almost matches with my syllabus.You are my DAA exam saviour

[@sripeddada8708]

Hahahaha Even mine😘😘

[@tejaswidutsharma6819]

my too

[@hotaru6765]

me too....in my case it's ADA subject

[@comedyvinesvkb2721]

Peddinti Kartik cmt Ĺugj

[@maheshvangala8472]

Even mine too

[@ARSHABBIR100]

sir, I have gone through various videos on this topic but your way of explanation is the best among others. thank you very much

[@anything1154]

Tomorrow exam 😅

[@JPremchand]

Same 😂

[@linnhtet001]

Best youtube-tutor ever...Thank You very much Sir!! Learnt a lot .

[@EXO_and_ENHYPEN_GaveMeBirth]

THE BEST TEACHER EVER !!! VERY WELL EXPLAINED #THANK_YOU_SIR !

[@kausikdevanathan192]

Thank you so much for your explanation sir, it was very clear and left no room for ambiguity. Really appreciate the efforts you make for us! Thanks again!

[@SmitaWagh-zm2jg]

15:40 direct formula

[@rawdreen]

Thank you! Today we have a Final exam and your lecture is very well explained!

[@prashantkaushik7063]

I highly recommend his udemy courses. He is possibly the best Algorithm teacher on the internet. All the complicated things were explained with ease.

[@shresthmishra9329]

is there any difference in the videos available on youtube and the videos on udemy course?

[@ravigupta4252]

It means you guys don't know about Ravindra babu Sir

[@microsoftiitm1537]

@@ravigupta4252 chutiya he voo

[@dhruvgovani2105]

You are saving lives of so much engineers sir , keep doing..

[@asrorbekorzikulov1764]

Thank you, Sir, so much. Today, I performed very well in my Algorithms exam only because of you. You are the best instructor ever 👍.

[@marinietao7352]

++

[@venky3867]

- -

[@gourav1163]

* *

[@fredflintstone7924]

You explain it in such a clear and simple way, finally i understand it, thank you very much!

[@sanilasabu5864]

Thank you for this amazing lecture sir.. Wonderful explanation. Clear.

[@harshraj22_]

wow...... This was probably the best explaination video on 0-1 knapsack problem on you tube (even better than the one uploaded by geeks for geeks ). Thank you so much for this .

[@_outcyrptolist]

Assalamualikum Sir ! Your videos are precise and to the point ! Provides decent understanding of the topic ! No words to thank you .

[@Shantisingh-tz5sr]

You are God Of Algorithms sir...Take my Humble Regard🙏🙏🙏🙏🙏🙏🙏🙏🙏

[@samaypashine]

It is best explanation video of knapsack. Thank you sir!!

[@theog6494]

you have a very soothing voice. I was stressing about this, but now it both makes sense and I have been calmed

[@beautyandbytes_24]

Sir why did you stop uploading videos you are great please continue it 🙏 dsa , java, courses etc. all my concepts are clear by your videos. I humbly request u to start uploading again.

[@savirc84]

His course available on Udemy

[@MichaelJohnson-Moonlight]

It was easy to understand. Thank you, professor.😎

[@hiteshbitscs]

Incredible sir :) In my college these kind of topics remained at the end and never taught...and taught hurrily as instructor wanted to run away from the situation...and this happens to big colleges also sometimes... thanks a lot for teaching me... real Guru :)

[@ernaldshehaj3066]

I thank you so much for this. I could never understand the lecture of my university, but you sir saved me. I cannot thank you enough.

[@the_mia_mia]

Wow, thank you so much, I've been struggling with this and you explained it so nicely!! Excellent job!!

[@kavithapriyacj4868]

Best and simple method sir.. thanks alot..the everess time consuming short and crisp method.. hatsofff sir 🙏🙏🙏

[@affafa100]

This might help somebody: In the last row of tabulation method, the formula basically says we are checking the max of: 1) the best profit we have till now for a bag with weight w, versus 2) if we put current item, the profit we could have + the max profit in remaining bag capacity we calculated. So, for e.g. consider 7kg bag. 5kg we put for last row item. Remaining 2. What's the best profit we can have with that 2kg.

[@samhita2917]

Hey, we do that formula just at last row right..??

[@affafa100]

@@samhita2917 Yes.

[@saisilpabijjala7046]

Living God of data structures and algorithms...thanks a ton sir 😇

[@PTM1008]

So much efforts have been put in. Thank you so much for such great explanation and content! Pace of explanation is excellent!

[@shrimp8594]

I'm dumb so I have to pause the video to process the information but in my zoom class I can't do that . Hence, I'm left understanding nothing. Thank you so much, watching this made all it clear.

[@TsuharesuLuciel]

I liked the explanation of the formula and how it works, but I missed how that formula was achieved. I had to do some thinking of what the table really means and what is saved in there. For example, why am I getting the number from previous row and the column minus the current weight? Except from that this is a superb explanation. Thanks so much!

[@scrycrystals2129]

Thank you so much, never felt this good while taking a lecture ❤