0/1 knapsack problem-Dynamic Programming | Data structures and algorithms

In this video, I have explained 0/1 knapsack problem with dynamic programming approach.
Given a bag of a certain capacity, W. Given some items with their weights and profit(values). How do you fill this bag so that you get the maximum profit?
See Complete Playlists:
Placement Series: • Placements Series
Data Structures and Algorithms: https: • Data Structures and Al...
Dynamic Programming: • Dynamic Programming
Operating Systems: // • Operating Systems
DBMS: • DBMS (Database Managem...
Connect & Contact Me:
Facebook: / jennys-lectures-csit-n...
Quora: www.quora.com/...
Instagram: / jayantikhatrilamba

[@furkanozbudak4440]

Your explanation is the best compared to 3 other higher-quality teachers I watched on 0-1 knapsack problems.

[@sanketkoli2958]

​@@ay9523 his explanation with solving seems difficult came to Jenny Mam understand successfully

[@amancollege9064]

same

[@lakshya.feel2207]

true

[@gamerzvilla8217]

Yes , absolutely right 👍🏻▶️

[@DunkMuvhimi]

true!

[@zantramte3515]

I have exam, so i was looking for a perfect video where someone explains 0/1 knapscak. And i finally found it. Thank you so much, you helped me a lot!

[@abdurrehmanansari2005]

27:14 there is an mistake it's (1 0 1 0 ). you can cross verify if we are considering the object ( 1 0 0 1 ) its exeeds the knapsack capacity.

[@JitendraSingh-qd7jk]

True I was thinking the same

[@AnuragKharade]

Yes u r right bro

[@AnuragKharade]

Actually 3rd and 4th value was swapped

[@hrushikeshmandekar6572]

आपका बहुत बहुत धन्यावाद 🙏 आपकी मदत से ही हम ये सीख पाए👍 आपने बहुत ही अच्छे तरीके से बाते रखकर समझाया हे इसीलिए आपका फिरसे धन्यवाद 🙏 esse he gyan प्रसारित करते रहिए, Bhagvan apka bhala kare 🙏

[@d.singhadda1605]

Thank you so much ma'am, This is the best explanation of 0-1 Knapsack problem on youtube. This video cleared all of my doubts, Keep posting these videos divyanshu singh

[@sachalraja1054]

imagine having ma'am jenny and sir. varun singla as teachers at the same university.....all students will be toppers :)

[@a.m.4154]

Jenny comes out on top for this one. Strangely, this is the best explained/understood video on this topic.

[@sachin1738]

Mam This Is One Of The Best Explanation Available Of 0/1 Knapsack Problem Available On KZbin. Thank You!

[@deveshdubey6776]

i understand the concept but in the end i never get the intution behind these logic..its more or less mugging up the process like what we have to do next..don't know about the other but if there is another problem same or little bit different from this i need to again check up the solution. btw thanks mam for explaining the process

[@technicalspider2547]

I am a seller who has a bag which can contain 10 kg weight so in order to maxmize my profite I am selecting those items in those ratio

[@ddmasterdon]

Follow books for understanding the full proof and the formal algorithm.

[@scuba485]

She has explained well enough.not sure what you can't understand. For every cell it's a choice between picking that or not picking that and comparing the profits

[@deveshdubey6776]

​@@scuba485 bro it was a year-old comment and explaining the intuition behind the pick and nonpick and how u arrive at it is what I want to know at that time... solving 10 questions on 2d dp anyone can get the process in their head, from a beginner pov arriving at logic is the toughest part and that is the thing I expect in the video that I didn't get that's why commented it.

[@bhagatalisha]

Try watching from take u forward, he teaches coding along too

[@kunalgoswami2495]

only u have made me explained mam. great respect ... everyone is talking shit. Either they are making memoization tabel or they are explaining code.

[@sanjanams9676]

Madam you are wonderful your teaching is awesome

[@SunilKumar-yq2bz]

Mam , Your voice is sooooooo, sweet .. I want to learn forever . Every time a new thing .

[@PulakMehta]

Such an amazing video explaining the topic. Thank you so much. Watching it one night before my exam. Very helpful..

[@NandiOnTheWheels]

your starting 2 sec i'm seen 4 times😜 and seriusly best lecture ever seen in this topic 👏 thanks for your valueable time to spend for global students 🎁

[@sundarrajgangshetty8561]

Thank youuuuu sooo muchhh mam for every video of daa❤❤❤

[@bhargavdasgupta6580]

Very nicely explained. Although I don’t think the sorting of the items according to the ascending order of their weights is necessary.

[@rochakgupta7231]

keep it up ma'am Aap ke bhi bahut jaldi 1 million subscribed ho jaye As I wish ...

[@JennyslecturesCSIT]

Thanks for your wish.... Working for it... So that your wish can convert into reality

[@shubhambohra2643]

Nicely Explained

[@shrikarnani2100]

good explaination and looking good mam!!

[@pranjalgupta9427]

Nice explanation 👍👏😊

[@seemabkarim8674]

Aoa mam, your all videos are very amazing, but i want to say one thing to you, kindly must add one thing in your lecture and that thing is to explain that why we study these algorithms, and where these algorithms will help in our daily life

[@heathledger7291]

congrats in advance for 100k

[@suhailgour6664]

Thank u so much Keep going mam

[@deviyaswanthdarla1537]

At 21:04 ,In the formula it should be w-w[i-1] , as array starts with 0 index. When i = 4 , w[i] gives doesn't exist at all

[@prakhar9886]

no this is actually correct in all books

[@mohitranjan8876]

Thank you so much maám for such a great explanation. Please make videos on compiler design also

[@thioMusiccollection]

u are extremely different beauty full teacher

[@shakhwathossain7947]

love from Bangladesh

[@ishusworld.927]

1010 should be answer as last one we are not selecting ?

[@gyanendrapandey7394]

Thank you ma'am

[@mayankrai2001]

P=(11, 21,31,33) W=(2, 11,22,15) C=40 N=4 0/1knapsack problm mam plz solve Q

[@ithinkiam3480]

which is best book for algorithms?

[@ArunMankar-g5w]

Ma'am Can you please give the formula for max term Who to extract the MAx term

[@nithishnithish6597]

if the weight is like 21,42 then how we conisder the boxes

[@ay9523]

Hey Jenny did you learn this from Abdul Bari video ? 😅 looks almost similar example ...anyways good going

[@ganeshsharma6326]

Just wow ...the best possible way u teach❤ ....I sometimes just think how good teacher u r and on the other side same age girl doing shit over tick tocks.😂

[@JennyslecturesCSIT]

I am just trying to give my best. 😊

[@ganeshsharma6326]

@@JennyslecturesCSIT that is why people like u the most.✌😊

[@JennyslecturesCSIT]

😊

[@EntertainmentVEVOrock]

Right...

[@everythingwithanirudha]

one of the worst problems in dsa

[@codingjony7400]

Your mom is one of the worst $Lut in Your city

[@everythingwithanirudha]

@SurfExcel-ms5vv 🥲

[@tarunkhandelwal1101]

@SurfExcel-ms5vv😡

[@suhanisolanki31]

You are right, I didn't understand

[@everythingwithanirudha]

@@suhanisolanki31 watch multiple videos, paper me watt lagege bhai

[@fastwork1396]

We want more videos on DAA .....well explained and you have make this topics easier for us. Thank you

[@techmunda7109]

Please make videos in Hindi or try Little mixing..

[@sushanthraju3215]

ma'am u just saved my day, tomorrow is my exam.

[@nehagowd327]

Same here 😂

[@reelscompilations2064]

Kottaya sappu

[@AnuragKharade]

Jenny mam happy valentines day ♥💖 and i love you😘 💞

[@mehtabhabib]

Awesome tutorial, very detailed explanation: a slight correction in P and W at top of table... P={2,3,4,1} and W={2,3,5,6} the values at index 2 and 3 is swapped for both P and W...

[@Mithu499]

correct bro

[@dishantzaveri6017]

can you explain this?

[@ers-br]

Thanks... I was implementing here and the matrix was not the same... I was getting mad :)

[@elikanest6027]

she sait it should be ascending order by weights

[@blackpanther801]

she took w in ascending order

[@kamleshnaik1290]

I don't know this happens with me or every one .... The same concept thought by other teachers on youtube is not understanding... But when ma'am teaching the concept it is perfectly understood 😂😂😂😂 Thank you ma'am😊

[@parastewari5697]

I feel the same....

[@harshpatel3989]

Now that is called attention😂😂

[@rehankarol7453]

Jenny mam is awesome

[@kamleshnaik1290]

@@rehankarol7453 😂😂

[@davidjonson303]

Wahh betai tu toh moz kar diya Line maar rahe ho...😂😜

[@zubairkhan72762]

Thank you so much ma'am, This is the best explanation of 0-1 Knapsack problem on youtube. This video cleared all of my doubts, Keep posting these videos.

[@solobiker5235]

your explain is good.. but don't use your native language, We can't understand it

[@JennyslecturesCSIT]

okiee

[@Sourav9063]

6:33 No, it doesn't need to be in ascending order!!!!!

[@abdullahalmasum5542]

*I think* it should be in increasing order since we are giving priority of each objects so it's better to write that way.

[@Sourav9063]

@@abdullahalmasum5542 No, the algorithm works whether it is sorted or not. Sorting the linked value is not easy to program.

[@abdullahalmasum5542]

@@Sourav9063 you are correct,bro. I made a mistake but learn something good. thnx😊 The answer is here also: stackoverflow.com/questions/29853579/do-you-need-to-sort-inputs-for-dynamic-programming-knapsack

[@amarthakur093]

@@abdullahalmasum5542 Just a suggestion. If you understand the algorithm instead of remembering the steps or formula, it will be easy to get why the order is not important :) . Most of the online lectures I found don't do this.

[@_Aditya_Raikwar_]

N=30 given h to 30 columns banane padenge ese to Puri copy bhar jayegi. Koi solution h iska??😢😢

[@pathe6158]

Good Question 😥

[@az7219]

i love wen she speak indian in middle english

[@amanwadgaonkar9615]

the final answer will be 1010 please check it once

[@ohhpeejoshi9110]

yes you are correct, i also got the same

[@sagniklaskar3493]

Watching this 30 min before the exam 😅

[@sumedh87]

Ma'am the method that we have been provided in our university book that we usually refer is so long , whereas yours method is simple and short which I would like to prefer it , but my question. is ,Will I get full marks by referring your method in exam?😅😅

[@SRK8338]

Placement hogya?🤔

[@ketankhandelwal8626]

What if w is very large, like 20-25?

[@reliablerupak6906]

Jenny mam ,Iam learning alot in DS and DAA from your lectures. Thanks alot to you for your great work on providing best way. I found 0/1 knapsack problem please look that we would have xi={1, 0,1,0} you have written there xi={1,0,0,1} .

[@sowjanya79]

She checked the set given in the question

[@FarmanOfficial777]

This is what for i was exploring comments thanks man

[@AnuragKharade]

Yes u r correct bro

[@amannny13]

@Jenny's Lectures CS IT Mam, mai itna paisa kamana chahta hun ki mujhe aap mil jao, wait for 3 years , ek baar graduation hone do, khud rishta aapke ghar launga. People would think i am simp, but this is pure admiration for the work you do. ILY

[@wizard.01]

She's already married

[@saichandu8178]

One doubt. After subtraction why should we go for previous row

[@srikrishnabejawada3126]

Mine is also the same...🙄🙄🙄

[@sadbinshakil1955]

Its just amazing. So much love and respect from Bangladesh

[@ankursingh9415]

aap ka jenny nhi genius hona chiye tha badal lo plz. thanks for clearing concept so smoothly.

[@raghavchandel1835]

After searching many videos I have find the simplest and easiest way 👍🏻 Thanks mam ✨

[@amarnathyadav9657]

If total weight is 20 than

[@AnuragKharade]

Mam you should add brackets over there m[I, w]=max(m[i-1, w],(m[i-1, w-w[i]]+pi)) 👆 👆

[@rd_HIND]

Good teachers need to be valued. Subscribed ✅

[@yours_madhu_here3905]

Thank you...Thank you...emcheppagalam inthakanna.... there is no machines...&No formulas to calculate the wait of your knowledge..maam...your are an absolutely A God made..milestone...for me... Every before day of my exams... You are the one & only hope to me....maaam.....we sending the lots of love from me and my friends...for you maaam....finally...we simply...saying with....most weighted hearts 💖 just one word...We are really thankful to you 😘 maaam.... Thank you for teaching every concept about data structures....Java...c...c++...what ever you said.... U r like the heaven to every pass aspirants...from the present b.tch students like me..... 💖thank you...maaaam💖from AP...STUDENTS🙏

[@thefuntech2810]

Honestly, I had seen a lot of video of knapsack problem (0/1) .But this video explains my every doubt . I don't want to take your more time to read this comment Overall you explained very well !!!

[@permmy]

The second day researching on how to tabulate this problem and I've found the solution here. Well explained! 👏👏👏

[@chittaranjanpatra6132]

1010 will be the items selected 1st item and 3rd item. correct it mam

[@pavanms9472]

Plz use dark markers 😢

[@Morimove]

As a seller who has only 8kg bag at shop This video is very helpful ☺️👍

[@MonirHossain-dn4fe]

Jenny apu, All i understand. But, How you get the result , its look difficult for me to catch it. Overall, your technique like as my favorite madam Rahi .. Outstanding. Thank u so much!

[@akshatpareek2189]

Mam if 2 value of weight is same then how to arrange them in ascending order either we have ascending them according to first come first put or Higher profit will written first

[@akshatpareek2189]

Mam please reply quickly i have to solve my assignment

[@saptarshidas979]

You are just awesome mam Wish i could have the authority to my college i would have battled with my teachers to bring you in as our algorithm teacher Rock solid teaching technique God bless you MAM tons of love from me to your hardwork Thank you so so so so so much !!!!!

[@harsha1670]

what are you doing currently?

[@madhukiranattivilli2321]

{1, 0, 1, 0} -- the weights (3 + 5 = 8) contributing to max profit (2 + 4 = 6)... not {1, 0, 0, 1}

[@nishantshrivastava8937]

Well the answer is right because the valve of x is already arranged in question and we have to answer the question according to given valve

[@madhukiranattivilli2321]

@@nishantshrivastava8937 Yes -- agree At the time of writing my msg, I didn't notice that Jenny had intentionally sorted the weights -- so I took table data as the truth and input as typo. Later, I realized it is unnecessary to sort -- whether we sort on weights or costs or don't sort -- 0/1 knapsack gives same result -- as it is based on dynamic programming

[@karansrivastav1802]

Dear mam , with the method it is easy to solve the problem but if the weight value=17 and n value=5 so it is getting trouble please help me on this its a humble request i am showing u the proper questions that is --solve following 0/1 knapsack problem where n=5, (p1, p2,... , p5) = (16,12,2,5,6), (w1, w2, ...,w5) = (7, 5,3,2, 8) and m = 17.

[@ShaileshKumar-gn3pd]

Hi Jenny, Thanks for videos on Dynamic programming. you are doing a great job. I have one question from where we got this formula ? How it was derived?

[@530gannisai8]

😂

[@rohandevaki4349]

your explaination and tricks are just awesome, that is why people come to learn these lectures from youtube even though they learn from their Universities

[@annepuvijay3743]

Thank you, I could recall the problem implementation with your explanation... Small correction if u can consider is..The formula given to fill the cells will not work for the cells in initial columns where that row's weight is less than that column's weight. Try applying the formula to the cells where we have 0s filled. In that cases, we can copy the values from above rows which ofcourse u have covered in explanation... Thank you...

[@sarojcs3535]

Wow Ma'am. You are best explaining these complex theories in so simpler manner with detailed explanation that gives us in-depth knowledge with complete understanding of the concepts.

[@FeeconOfficial]

U r not following the steps. Jumping straight to the tabulations!!! DP is based on recursion. U should have started with recursion. How can u make the table at first without knowing the initial conditions??

[@parvezahmed4u]

KZbin to Me :- Wake Up Early In The Morning And Do On Thing Learn Something From This Teacher #HighlyRecommended ♥️ Me To KZbin :- Yes Sir..🌹

[@indianguide259]

Brilliant lecture. You explained exactly in the same way how 0-1 Knapsack algorithm formulated. I am able to relate the complete formula. Helped me to avoid my phobia for DP.

[@vishalchauhan9832]

Mam is it necessary to take weights in ascending order?

[@vishalchauhan9832]

@@docd5949 it is not necessary bro.

[@Quaiqiai]

Not necessary.if it is not done too we get the same thing

[@vishalchauhan9832]

@@Quaiqiai yes bro, i have done this question by considering both order. The answer will be same..

[@learncseasily3385]

plz reply why profit has takken 2341 it was given 2314

[@anishdas6511]

According to weight

[@adarshkumarverma879]

mam aap thora haste hue video banaya kegeye ... sikhne me aasani hote hai

[@parmarprakash4621]

Pehle pehle thik raha end me magaj ka dahi vadaa ban gaya 🥺

[@rohithrr7079]

i lost hope on the exam but this particular video boosted me like anything!!! thank you!!

[@harshpanwar1550]

Thank u so much Ma'am😭😭😭😭🙏🙏🙏🙏. Aapke explanations amrit ki tarah hai.🙏

[@ADITYAJHA-k8l]

madam what will be the solution if give weight is greater than m given value like in this question : find optimal solution for 0/1 knapsack problem(w1,w2,w3,w4) = (10,10,12,18); (p1,p2,p3,p4) = (2,4,6,0) and m = 15. can you please make a separate video for that

[@ayushbhanu5008]

I have a query ,in case of coin exchange for 0 column you have taken all 1 but here you are taking all 0 and I think both have same condition .please explain

[@rajat1548]

same doubt

[@Drstrange2003]

Video quality very low ……

[@ramkudali3694]

Guys according to problem and which mam told logic when comparing both at 3rd row 5&6 columns getting different values did you observe??? If you get same like then mention me l... Thank you...

[@rajnaren4912]

Good explanation but logic seems to be slightly wrong. For example, (2, 8) value should be 6 as we can have 2*4 -> 2*3= 6. Why 5? Seems like taking value from above row and adding seems to be wrong, you need to take it from same row. Also, adding 0th row and column is not much useful. Thanks for sharing your knowledge!

[@aatifnazar1766]

Coming here after watching 2-3 videos and no one does it better than Jenny mam. Rock on ma'am!

[@beginner6519]

same bhai

[@uditkumar370]

Yes bro correct ek dam🥳

[@ritickmadaan]

Glad that I chose this video to understand the concept, nicely explained👌

[@aosis]

I like your other videos but this time you are not explaining how things are working and only focussing on the textbook solution. Why this can be solved using DP? Why did you choose individual weights and total knapsack capacity as two parameters while making matrix? Why did you jumped directly to matrix making?

[@praveenthakur6402]

Thanks for such a great lecture, the best explanation of the 0-1 Knapsack problem. Please start posting the algorithm also.

[@ShubhamSingh-f7v]

I can add items in my bag with common sense,i dont need this algorithm and table😤, just by looking at it i can say what will be the maximum profit (because it's too hard to solve through formula)

[@omoregbeekhator4517]

Thanks for the videos but can you just add the code snippet just like you have been doing in some of your videos. Once again thank you very much cos you have broaden my knowledge on data structure and algorithm implementation. #youarethebest

[@Smile-si8xv]

You are the best you know 🥰

[@robomanithan2216]

It was a wonderful explanation ❤ it can be easily grasped by the people. Thank you for your great effort. Do more videos like this.

[@kanishtyagi3148]

Question:- P={11,21,31,33} w={2,11,22,15} c=40& n=4? I am unable to solve plz help as soon as possible mam.

[@madhukiranattivilli2321]

Why should we sort the weights when DP is anyway gonna compute max_cost for all combinations of weights and knapsack capacities?

[@milton2345]

You are better than Abdul sir