01 Knapsack using Recursion | Building Intuition

[@rimzb]

Thanks

[@rimzb]

This is a small token of thanks for the knowledge I have received from watching your videos. I have started studying DS and Algos all over again after a decade to prep for interviews. I used to get bored and demotivated after a while and the LC solutions can sometimes be tricky to understand almost to the point of giving up, but your explanations, diagrams and points are so easy to understand and remember. They are also addictive to watch, lol. The fact that you can keep your students engaged and interested in the content truly makes you an amazing teacher! I hope more people benefit and contribute to your channel :) Thank you so much for your hard work and effort!

[@Sky-nt1hy]

wtf i seriously don't understand why you have only 38K subs. I've been working on Algorithm on my own for the last 6 months and have seen more than 100 channels. They're all great but I have never seen a channel better than yours. I will spread this out to help more people. Thanks always bro.

[@Sky-nt1hy]

maybe you should do more ad or some commercials this channel is extremely underrated

[@techdose4u]

Thanks for your support bro :)

[@techdose4u]

Ad will cost good amount of money which I don't have right now 😅 So, I am relying on word of mouth to spread the existence of this channel. Thanks for helping.

[@Sky-nt1hy]

@@techdose4u Your sub# is too low for this quality. I am thankful for this channel so much! I will try to go over as much as possible before the interview. Always cheers!

[@dayanandraut5660]

Completely agreed

[@sridharanshooriya772]

You are a life saver! Even coursera course on dsa didn't explain as beautifully as you did. Reading out of a slide made it hard to understand. Your teaching method works like a charm! I'm honoured that you do these videos balancing your work life. Thank you surya!

[@techdose4u]

Welcome

[@adityasarin39]

This explanation is the best I have ever found for recursion! Covering each and every small detail, step by step 👌

[@techdose4u]

Nice :)

[@sanskarrawat1047]

Kabhi aditya verma ka naam suna h?

[@Luckyankii]

@@sanskarrawat1047 na sunnA HOGA PAKKA YE

[@PujaKumari-rp5sg]

Whenever I don’t understand something, the first thing I do is search for a video on your channel. Before watching your video, a sense of relief comes to mind because if your video is available for this problem, I know I will surely be able to solve it. Thank you so much!❤❤❤! People like me who was thinking I couldn’t do DSA, I’m now confident and solving DP problem . Next, the last topic is graphs for me 😊

[@hardiksrivastava6395]

This is by far the BEST explanation compared to all coding platform giants. Your videos on DSA are superb and to the point. Much much appreciation and love !! You are great !!!!

[@pramodsharma4508]

I think you should do more dp problems with their recursive solution first...it really helps in building the thought process of the problem...

[@techdose4u]

Yea sure

[@sommayghosh4617]

@@techdose4u yes sir ur way to approach the problem is very nice it helps to build intuition , please continue building this playlist!

[@yianchen1553]

thank you; you're a godsend. you have helped me understand so many concepts that i previously couldn't grasp.

[@AlbtzGaming]

You make us falling love in coding !! Thank you very much for your effort !!!

[@techdose4u]

Welcome :)

[@prabhatmishra6753]

I was very furious about English explaination but when I started watching him , his explanation is enough to understand you what actually a code wants from you as well as very clear explanation

[@techdose4u]

Thanks ☺️

[@nicknack9908]

This was a great explaination! Helped me a lot with my coding homework in university, which I could not solve. (Currently studying computer science in Germany.) Keep the great work going! :)

[@techdose4u]

Thanks for your appreciation :)

[@abhijitroy1958]

best explanation till now of knapsack

[@maryam1777]

Man my God keep you in great happiness.. YOU ARE MY LEGEND

[@haqinzmamul12]

Bro I scroll upto 10 times down videos on KZbin for dp there are so many great I watched all of them one by one but you're hero among all of them.... keep going you'll be remarkable one day

[@sridharanshooriya772]

The naive approach was explained intuitively. Thank you!

[@techdose4u]

Welcome ;)

[@123liveo]

This explanation is absolutely superb. This at the next one about memoization really helped. Recommending it on my uni algorithm course. Cheers!

[@kush-cp8kc]

thank you so much for this much detailed and pin poined thing ....it was really really helpful and the best till now... .

[@noc12]

I am following this channel when it has 10k..finally got what u deserve..congrats for 100k subs

[@techdose4u]

Thanks 🙏🏼

[@mikekibet1786]

Best explanation ever. I am subscribing this very minute

[@techdose4u]

👍

[@physicsmathsworld2033]

Brilliant Teacher ❤️❤️

[@ihsannuruliman3656]

this is a great channel, even better than I was thought.

[@大盗江南]

These videos are amazing.buddy. Just amazing...i finally understamd

[@techdose4u]

Great ❤️

[@malikwaseem1983]

This is explained really well. Thanks Tech Dose. I love your channel.

[@techdose4u]

Welcome :)

[@manoranjaniiit]

Simply awesome explanation

[@techdose4u]

Thanks :)

[@krishnasalampuriya1311]

Very helpful 👍

[@renon3359]

Thanks for the great videos man, I am learning DP from your playlist only, and I haven't done DP ever before.

[@techdose4u]

Great bro :)

[@techmoon_]

best lecture bro great explanation

[@techdose4u]

Thanks :)

[@ChandraSekhar-tr7sf]

Excellent 👌

[@shoumeshrawat1362]

You explain so well .. Thnk you so much

[@techdose4u]

Welcome

[@RCavivhal]

Thank u for this tutorial, great explanation. Really appreciate it

[@rehanakhter4813]

I am waiting for combination sum with all its variations. Please introduce it. Thanks for the good work.

[@techdose4u]

I will upload it someday :)

[@abirmoulick866]

Great explanation. I want to know whats the advantage of traversing array from back (n-1 to 0). I have seen it many times in other codes.

[@dineshothamkumar]

It is to satisfy the generic principle of Recursion that goes from N to base case. Here, the base case is N=0 that is no item to process.

[@rajatnagpure7445]

waiting for video on Travelling salesman problem. Be it in graph theory or DP playlist.

[@techdose4u]

It will come in graph playlist. I will cover those topics later. There are some topics left in graph. But everyone was requesting for DP to start ASAP, so I left graph for now. I will resume it only after finishing easier topics.

[@CodingRegion]

Thank you for this video💙 This is so helpful 🥺

[@devprakash5320]

sir, you explained it beautifully .

[@techdose4u]

Thanks

[@abhishekkumarjhariya1340]

Great explanation .

[@letsdoeverythinginoneweek9398]

thank u sir for making this dp series is this dp series is enough to clear our all dp concepts

[@techdose4u]

Almost all for interview

[@amitp277]

great explanation 👍🏻

[@bhawnasingh8114]

Best explanation!!

[@techdose4u]

Thanks

[@shiyamabhisak4778]

This is the best explanation for recursion I,ve heard till now ,Your way of explanation is very nice and helpful for me to understand each and every step in detail.

[@techdose4u]

Thanks 😊

[@rishabhratan2925]

wont it be (n-1) in the skip case?

[@naman_goyal]

Very nice

[@techdose4u]

Thanks

[@DEVANSHGOEL-dq1wh]

Thank you very much

[@techdose4u]

Welcome :)

[@sridharanshooriya772]

14:06 if we skip the item, the profit will obviously be lesser of the included right? Or... Skipped item will recur to its previous items and return the profit?

[@lakshmivishnu6594]

Excellent, Thank you!!!! :)

[@techdose4u]

Welcome

[@jagdishsahoo8232]

Sir your explanation is awesome...It will be best if you can provide the questions links of the problems of the theory covered, from which we can practice :)

[@techdose4u]

👍🏼

[@harshitchoukse2602]

The base condition should be if(n

[@kr_ankit123]

you are right bro👍👍

[@harshitchoukse2602]

@@kr_ankit123 but later on , I understood that he is explaining from 1 based indexing.

[@ajithpalani5139]

Clear cut explaination,Favourite teacher ever.Keep Rocking sir.Thank u sir🔥😍🔥

[@techdose4u]

Welcome :)

[@rshmvarma]

This was amazing.

[@techdose4u]

Thanks :)

[@dayanandraut5660]

if N = (length of W)-1, then your base condition should be like this if (N==-1 || W==0) return 0 if N = (length of W), then your other condition should be like this if(wt[n-1]>w)......

[@nahman1105]

Great video, thank you! How could I also output the volume along with the value of the knapsack?

[@Trishul-Industries]

his explanatation is much more similar to Aditya varma explanation for same question. Both are super

[@Kaa-rj4on]

Do you have the code in any git repo or somewherer...?

[@rangapavankumar79]

If we use this in any online contest it is able to pass all the test cases?? As the time complexity is 2power(n)

[@techdose4u]

No it won't pass all test cases anywhere. For that you need to use DP. I will be explaining how to write DP code in next video.

[@mdimranhosen6674]

💚

[@techdose4u]

Thanks 😊

[@mayankchauhan6680]

Thanks, Algo Buddy. By the way, this one is much like backtracking.

[@techdose4u]

True :)

[@extraspecialgyan7052]

op sir ji

[@lakshmivishnu6594]

Hey, Are you planning/giving any private tuition ( one-one online or in-person ( especially focusing on the effective c++ by Scott Meyers approach ) on C++? If it is so, is it possible to send you a private message to discuss further?

[@pranavyeleti3499]

in recurssion can we start from i=0 to i=N-1

[@nitinmahajan3320]

Why do we start from last element of array (N-1)? Naturally I will start from 0th element of array till N-1. Are there any benefits or challenges in thinking reverse?

[@techdose4u]

You can start from beginning. No problem

[@bruhbrh7266]

i am getting wrong solution with the base case N==0, it wont calculate the 0th i of the array (the first element). putting n

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@rishviks8987]

Sir, I think the same could be done using backtracking 🤔

[@ADITYASINGH-og9ml]

Make a video on painter partision problem its difficult to solve

[@techdose4u]

Already made

[@259_parthpatidar9]

wow

[@techdose4u]

😊

[@mahipalsingh-yo4jt]

sir I am not form cs background , so how much time it will take to cover cs subjects for placement preparation. I have watched your video in which you said to complete them in 2 days per subject. Will 2 days be sufficient for a placement in big companies. Please reply.....

[@techdose4u]

You will need longer time. 2 days is just for revision. You can finish a subject in 10 days.

[@mahipalsingh-yo4jt]

@@techdose4u thanx sir ..

[@matthieuguimard2236]

Your video is very clear thankyou for making it. However i am trying to adapt it in order to save the optimal configuration the recursion find. With your code I only have the maximum profit but the configuration is transparent. I thought abour builind a binary tree but i am struggling with it. Would someone has an idea?

[@techdose4u]

Hi. Building a binary tree ? Why

[@matthieuguimard2236]

@@techdose4u I want to keep the optimal decision tree. I understand that with your algorithm I have the maximum possible profit but i don't know wich configuration leeds to this maximum profit. I don't know if the binary tree is the good solution but it is just the intuition I've had. Each decison ( 'take it' or 'not take it') would create a new branch. When the algo is over, I would just have to parse the good configuration from the tree.

[@heybeachMIN]

I think there's basic-case a little bit not right, coz n could be < 0, so you need make n

[@dineshbabu3227]

Shouldn't the basecase be this?? if(n

[@dineshbabu3227]

I changed input as weights {4, 3, 2} and profit {7, 6, 8} Output: 14 when n==0 15 when n

[@gugli28]

the approach is same as printing all subsequence of a string

[@syedkaja2045]

understand everything but i cant understand the else case pls dry run the code with some example:)

[@techdose4u]

Else case has 2 options. You can include or exclude a current item. We will take that option which gives us maximum profit.

[@spetsnaz_2]

If weight of current element is greater than the available space, then skip it. If no of elements becomes 0 or the knapsack becomes full, then return; Else we can either include current element and go to furthur processing or we can skip this current element and go to next element for processing because this element may give us lower profit compared to other elements

[@syedkaja2045]

@@spetsnaz_2 oh ok i understand ;)

[@syedkaja2045]

@@techdose4u thanks :)

[@asashish905]

@@spetsnaz_2 how to check the may part?? May give lower profit part?? Can somebody tell me about the max method plz?

[@yitingg7942]

Recursion is indeed hard.. No matter how many times I have seen them and used them I am still so scared of them.... 啊😔😔😔

[@techdose4u]

Recursion is all about visualisation. Once you can do it, recursion will feel as easy as bruteforce method :)

[@audiobooksforyouspark]

wow

[@anonymoussloth6687]

base case should be N==-1 || W == 0

[@MathematicalCowboy]

Great explanation! However, this approach doesn't reveal the correct combination of items, only the maximum profit to be had by choosing those items.

[@tech_wizard9315]

6 months roadmap please to crack google for 2020passouts

[@neerajseth6566]

Profit(n) should be Profit(n-1).

[@Cloud-577]

Thank you so much