5 01 Knapsack Top Down DP
HTML-код
- Опубликовано: 8 сен 2024
- 0-1 Knapsack Problem solution using Tabulataion Method.
TOP DOWN APPROACH
Example:
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).
PROBLEM STATEMENT LINK:www.geeksforge...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Hey very good explanation, I agree on the comment that direct tabulation approach is not very intuitive to normal human mind, we have to build up the solution starting from recursion and memoization. Just one small comment, the tabulation approach is not top-down but bottom-up. It is called bottom-up, because we start the solution from base case (initialize matrix using base case) and build the solution to the top (t[n][w] in this case).
Oh yeah. of course I am glad you pointed it out. I messed up, those two terms have always been confusing to me !! 😅However our solution is still correct af, I am glad names don't effect the way you do things !! Let's just call one Memoization and the other Tabulation to avoid confusion. What I did in this solution is Tabulation. Thanks for pointing is out tho !! Keep watching and share ✌️
@@TheAdityaVerma I'd suggest adding a video after the introduction of the playlist that explains the difference between top-down (memoization) and bottom-up (tabulation). You can mention it in that video that whenever you say "top-down" in the following videos, you actually mean "bottom-up" or "tabulation". It's important that no one learns a wrong thing. Other than that, your videos are very helpful. :)
The videos are good, but even a minor mistake in standard terms also may lead to failure no matter the explanation is very good. You ought to add a frame at the start of each video that wherever you refer top-down, it is actually bottom-up, else, people will start losing faith. My intention is not from any means to hurt you, but since, your explanation is good, you need to be full-proof.
@@TheAdityaVerma So the recursive solution was top-down approach as we started at the top and kept making recursive calls until we reached the base case and then started returning values while the tabulation one was bottom up as explained in the comments, right??
@@stark_mark1107 Ya exactly.
I am working in IT for the last 7 years I have tried many tutorials for data structure and algorithm but no one explained like you. I really appreciate your effort. Please make the videos topic-wise from basic it can be paid or free.
Thanks a lot brother !! I am glad you liked it !!
I also felt the same way, thank you so much for time and effort Aditya Bhai. As you said all the youtubers just explained the tabular method but no one taught the same u r teaching i.e converting recursion into tabular method. hats off for your explanation and ideas. Keep uploading such problems and videos I am loving it.
I tried learning this from hell lot of YT channels like Tushar, Jenny, Apna College, Anuj Bhaiya, even MIT Open Courseware. One word, all are trash and I could understand nothing from them! Only a true coder like you who actually works in a company and who has grinded so hard to achieve it can explain this with such clarity. Tysm brother! 💓
This is just to let you know that this is the first time when someone has explained me "how to code" with such clarity! I am really very amazed and motivated today because of this video playlist.
Glad it helped you !! Please consider sharing the content with your friends or college to help this channel grow !!
@@TheAdityaVerma bhaiya yahi to prblm hai market me itna competition hai ki share karte wakt dar lagta hai actually nahi kar pata hu baki likes or comment to milega
@@TheAdityaVerma will definitely! keep on posting, love the vids
@@TheAdityaVerma Excellent Explaination. But in the GFG knapsack problem. The memoize solution is not accepting, while the top-down is accepted. There is a time limit exceeded error.
@@buzzfeedRED 0/1 knapsack or unbounded knapsack ?
Bro I am a 15 years experience engineer.. your explanation and determination to make everyone understand this topic hits hard
after 15 years why are you here for dp tutorials. i mean dp is basically caching. you might've already knew that.
@@muditkhanna8164 YOE?
This video is great having great explanation, having two minor mistakes. 1) Top down is actually bottom up. 2) At time 29:37 it should be be T[n-1][w-wt[n-1]]
yes exactly
Agreed
Why taking dp[n+1][w+1] for what that +1 please resolve my doubt
@@bokkamanideep9893 The size of value or weight array varies from 0(no element) to n (all elements) . So we have to select the size of tabulation table t[n+1][W+1] so as to accommodate all possible combinations from 0 size and weight to n size and W weight
Can you please explain why it would be w-wt[n-1] ? Isn't the second condition for the case where we are not selecting any element? When we are not selecting anything, what weight are we subtracting?
I might be wrong but this technique is called Bottom-Up (Tabulation) and the technique you taught in last video is called Top-Down (Memoization) technique.
I have learnt basic concepts from your tutorial and it obviously helped me to understand DP fundamental concept.
Thanks bro for your skills to share with us.
yes buddy yuo are right
this is called as TEACHING Dynamic Programming!!
great work Aditya! :)
Why cant I double like? This deserves a thousand likes. You opened a whole perspective of DP for me.
Using recursion first to explain and then coming to bottom up approach was a stroke of masterpiece. I've always wondered how to solve DP with tabulation but this DP series is a life saver.
Didn't realize the 40 minutes were over till you said that "ab aapko samjh aa gaya hoga". That's how well you taught.
First time i have seen someone connecting recursive code and tabular code like this, your method of teaching is just amazing.
In my 3rd year now, and till date I've tried to learn from so many different resources but nothing like these videos. A genuine thank you from the bottom of my heart for keeping shit real and free. Stay the same when you hit those subscriber milestones on YT because you will. And soon! ✌️💯
placement hui ky?
@@yogeshyts Haan bhai, 10LPA
@@damercy company?
@@yogeshyts It's an early stage startup man. :)
@Adarsh Chaurasia Hey thanks! :)
at 29:44 you take one time i as W and j as n while taking maximum .. completed 5 video and you explained very well..Pure Gem
I am a student in IIT , was finding it difficult to solve it many youtubers just doent tell us why we created table why we put t[i][j] = max something , but after listening to this one video whole Dynamic programming is looking easy kudos to the person , am a fan of you now
BROooo ....I dont know how to thank you ....I was really looking for this exact way of teaching ... and yesterday only my senior suggested me from IIT Guwahati to follow you ...and i wasn't able to sleep after seeing the way and quality of content you have provided ....i was so eager to learn and watch ....thank you so much , really .
One day I'll succeed in spinning pen like you.
it took me entire 11th and 12th XD
I can spin using both hands :P Thats the only thing I learnt during IIT JEE preparation. Of course its not enough to get into IIT lol :P
practice jaari hai bhai
There is a pen available that has spherical weights that move towards the end to create centrifugal force -- it makes spinning very easy. Its called, (what else) spinning-pen. There is another spinning technique where you pass the pen between all the fingers -- check it out in the 'classroom training' scene in TopGun. Who knows what I am talking about?
@@0anant0 you can spin any pen lol
It's easy to find good developers out there but hard to find a good teacher. Paper pen approach is best to connect with the audience, in making them understand why something is being done and what is the thinking process to approach a problem. There could be minor mistakes here and there in what you have explained (my observations, based on the comments other viewers have left) but if the viewers can pickup on those means you have done a great job already in developing their thinking and they are following along with your explanations and thats what a teacher does :) . You have reminded me of college days where friends just used to discuss and solve problems using our basic tools -- pen, paper and friendliness of language.
i have spent more than 4 months to only understand DP, But I must say that what you have taught in 4 videos, if i had see it earlier it will save my 4 months. very good explaination.
Bro noone literally noone has this level of understanding . the way you explained it was way better than anyone out there . in my case I never studied DP from any where 'coz I was afraid but now I am damn confident to solve any problem because now I know how to approach the problem . thank you so much bro .. and a huge respect to you . Aditya Verma OP
Hands down!!!🙌🙌 You're the BEST teacher ever!
No one has ever explained why of every single thing in DP, and you've done that ❤
bro why did u stopped uploading : ( , want series on graphs and advanced data structures too . your teaching is friendly , like we teach each other in hostels : ).
that hostel point was so damn relatable xD
He is dead bro 😭
@@mrsukki8158 stop spamming fake news
@@mrsukki8158 tera baap hoga, aditya verma nahi
@@mrsukki8158 aisa nahi hosakta
Code for all 3 approaches: Recursion => Memoization (Top down) => DP (Bottom Up)
//1. Recursive Approach
int knapSack(int w, int wt[], int val[], int n)
{
//Base Case
if(n==0 || w==0) return 0;
//Choice Diagram Code
//1. Choice to include item or not
if(wt[n-1] w){
return 0 + knapSack(w,wt,val,n-1);
}
}
//2. Memoize above recursive code (top-down)
int knapSack(int w, int wt[], int val[], int n){
vector t(n+1, vector(w+1, -1));
return fun(w, wt, val, n, t);
}
int fun(int w, int wt[], int val[], int n, vector& t)
{
//Base Case
if(n
In Memoization why your code is giving the wrong input when the vector t is declared globally?
is'nt it v[i] intead of v[i-1]
@@anonymous63066 No bcuz we are checking for the wt[] array....And it starts from 0 index. Here indexing for the matrix is one more than that of the input array.Hope you get it.
Can I please know why we require second else? when in If only we have the same statement?
Hands down the best explanation on DP. You are helping those who cant afford to join expensive courses online. Keep it up brother !! Thanks !!
Thank You So Much Brother.I Don't Think Anybody else is teaching the Crux of Dynamic Programming So well!Your Videos are Valuable for Beginners!
pehli baar top down ka matrix bana ke use kata nhi 😅😅
kudos to your effort, sir !! 🙌🙌
God level explanation brother !!! I was so afraid to start DP from much time. But when I started watching this playlist, it was so effortless for me to understand it . You made my day sir :) God bless you !!
I could learn and master recursion just because of you, otherwise I was always afraid of it, thanks a lot for your effort, couldn't learn things in college due to my health issue, but learning now and your videos are helping a lot, I am having 10 years of experience in IT.
Honestly, even if you pay a lot of money, you wont find the clarity with which you are explaining. Thoroughly enjoying it. Great work....Try making your videos in English also, your viewership will climb 10 folds...Also, your videos shows the huge number of hours you grinded to gain the clarity with which you are explaning. Great work and thanks a lot.
Thanks a lot for such a great comment brother. You made my day !! ❤️ Do share !!
Amazing explanation, I m final year student from tier3 college. I was shit scared with coding rounds as our teachers hv nvr taught us these things. Our clg placemnt was limited to Infosys TCS, finally after watching your videos I hv gained the confidence to try for Product based companies. I will surely meet you in person once Im placed in one of those companies. Love your work bro, please keep uploading videos these are really really helpful for students like me. Thank you so much.
So far I liked your way of approach ...the great part about your video is that you show one way of approach and than to counter that you show other along with the reason of chosing the later one....it's builds up logic very effectively....will make effective use of whole playlist.
Thanks sir 🙂
The initialization part can be done in O(n) instead of O(n*w).
Use one for loop (from 0 to w) to set t[i][0] = 0 and another for loop (from 0 to n) to set t[0][i] = 0.
haa but woh abhi main nahi hai bhai, main hai yeh DP😂😂
You're 100% correct though the rest of the algo is O(n*w) anyway so it doesn't really matter Asymptomatically
bro does it matter if I write outer loop for W and inner loop for N ???
Ab ate hai yeh log , jo padhane vale k samne usko sikhate hai .
kuch bhi...isse khaali 1st row and 1st column hi initialise hoga
after watching this video,I feel like ab toh apun hi dp ka bhagwan hai
thankyou so much ,I am able to visualize everything about memoisation and tabulation now
The amount of efforts put in explanation is commendable!
Thanks a lot sir!
Hi, great videos on DP. But I think tabulation, that is deliberately filling the table from the most solvable(or smallest) problem is the bottom-up approach. the backtracking with memo/caching is Top down, where we take the entire problem and keep hammering on it till it is broken into smallest solvable pieces and cache results for reuse
This is Epic 🙌, thanks alot sir for this
One of the Best dynamic programming course.. ever❤️❤️
Finally, I understood the lines of code. Earlier, I was getting an error.
Thanks!
at 29:30 in the bottom-up approach instead of t[w-weig[n-1]][n-1] it should* be t[n-1][w-weig[n-1]].
Rasik Mahajan was waiting for this comment
correct! Got me confused. Now it's all clear
Right, He should be more focused when writing code, I know it's easy mistake to make but we can't doubt him as well and start thinking to our self why is that.
This reminds me of dfs grid problems where instead of considering mx[r][c], they consider mx[c][r]. (mx = matrix, r = row, c = col). Has anyone seen this?
I was searching for this comment , I was confused too -_-
Great Lecture on DP. Thank you very much. I am a newbie to DP but I have idea of other DS and recursion. I thought that DP is gonna be tough, but you made it easier for us. The way you approach a DP problem is awesome. I will remember your each and every words.
DP jaisi h waisi likhoge to DP ka solution likh loge.
Never directly start with tabulation.
DP is enhanced recursion.
Agar recursive calls me tree bann rha h aur overlapping subtree dikhe to DP lagega. Aur question me optimal pucha hoga
I was searching for such a RUclips channel on dynamic programming that would help me think how to think and I am glad that I found your channel.. More power to you !!!
best DP explanation till date either on free platform or on paid courses. :)
You are one of the greatest RUclipsr for the learning data structure. I was having a lot of difficulties understanding the recursion. Now a concept is quite clear. I think you should start your startup similar to algoExpert. You have great potential to explain everything which no one has. Other people just discussed solution but you discussed how to reach that solution. Could you please start the videos for "FAANG" companies? Complete tutorial. I will never mind taking a paid membership for it. I solved more than 50 problems in recursion but no one tells about the choice diagram. Please let me know how did you learn those things? Did you refer to any book?
Finally someone who is teaching how to code a solution , rather than just telling the solution most of the youtubers and all my university professors just show the algo and don't give a damn about code , I am ready to pay for a course of such caliber
just one word bhaiya, just one:
BRILLIANT!!!!
U r too good man... I have viewed most of the utube videos on dp but no one has xplained in so much depth.. U have my respect🙏
Fadd explanation hai bro.Your concepts are crystal clear, recursion par bhi playlist upload krdo brother
bhai kya he bolu .majja he aaaa gaya ,10 times batter than college professors. recursion sikhane ke kiye eek video series bana do pls.
Thanks brother, Do subscribe and share, that keeps me motivated to do more !! and yeah its in my to-do list.
Everything u taught in this video is on point love it🔥🔥🔥🔥.
Bro.... Really from my heart.... I thank you!. I have not been able to pass coding rounds due to questions in DP. I really feared. But the way you have explained.. just awesome!. Please go on!... Thank you! :)
You madee brave enough to encounter Algorithm and coding ❤️
bruh Dil se thank you...You made things crystal clear in one go. way of explaination is also good. Hope to complete this playlist in 10 days.
Superb Bhaiyya while other youtubers are just making us mug up the code, you came up as a live saviour! Keep uploading. Also can you please make videos on general topics like how and where to study theory subjects, how to clear online test etc. It would be really helpful
The best among the ones which exist...Explaining such a hard topic in a very simple manner. Hats off
Thanku so much for this amazing lecture.......!!!!!!
i -> n and j -> w please take care of that, well explained thank bro
Amazing bro, so easy to follow. Keep rocking. Felt like I'm in my college days, some of my topper guys explaining me :)
Bhai alag level pe samja rahe ho. Most of the people don't understand how to teach. This is the perfect example of how one should teach anything.
Thanks please keep the work and continue uploading videos
We are just awesome ..Lot of respect and lot of love to you sir❤️
ME Wayne We?🤣
I mean u sir
Best explation of 0-1 knapsack in youtube
It helps me a lot..😊😊😊
Great effort by u Man....Thanks a ton..!!!
Waiting for the recursion playlist to be uploaded...I request you to please do it asap..
Till then if you can recommend any material to ace recursion would be a great help :)
Will upload more video in the month of may !! Till then keep on sharing and help this channel grow + that keeps me motivated to make more videos !! ✌️❤️
well explained by you sir. A few days ago I have seen the solution of knapsack in algoexpert ds algo series. At first time I couldn't able to understand what and how the things are going because the problem was started itself from top down approach and today you have cleared my all doubts and the multiple solutions of it. I'm very thankful to you. 🖤
bro ur just too good
Thanks brother, share to help this channel grow !!
This was so easy to understand. You made this scariest topic easy. Thankyou so much sir for this tutorial 😀😀🙏🙏
Hi bro,
Great initiative.
Please make videos on graphs as well :)
It will be a great help.
You are doing god's work. Very thankful to you. You tell us what we are trying to do fundamentally, which make it easy and quick to understand as compared to using definitions and bookish language.
edit: I find it better to initialize value[] and wt[] arrays to n+1. this way there is no confusion in indexing it t[][].
Hi Aditya, Thanks for the amazing explanation but I think at 37:26, in the 'if' condition, we should reduce the weight of the bag with previously filled item while comparing the current item's weight like 'wt[i - 1] < weightOfbag - t[i - 1, weightOfbag]'.
Yes... I also noticed same
no, it's not required, the current item's weight that is wt[i-1] is being compared to the jth value at that time, that is the current weight the bag or knapsack is holding.
thanks a lot bro i am really loving the series.....I cant express how i am feeling after understanding everything
Hi Aditya,
I had one question, how does replacing n with i and W with j work? because we check from end of array if the item's weight is < W ie (wt[n-1]
Did you figure it out? If yes can you reply with an answer.. I have the same doubt
200% right. Nobody could explain like this. Hats off to you man!!
aren't you mistaking iterative solution saying it top-down which rather should be bottom-up ?
God level explanation. All doubts are cleared. Please make a playlist on graph.
Is there any specific reason you took t[n+1][w+1] and not t[w+1][n+1]?
No, Other way around will work too !!
i never ever thought i would be able to understand tabulation(bottom-up solution) but its all becuz of you, i got this .thanks alot man
bhai aap kaise samjaathe ho ..gajab hai ... I have seen multiple videos on DP and mostly they just repeat the existing solution, but the way you mapped recursive to top-down is just amazing. I always struggled to find the top-down but never realized there is one-one mapping with recursive
Bhai recursion sikha do acche se ek bari....... fir DP halwaa lagegi
Will be uploading more videos in may till then keep sharing to help this channel grow + thats motivates me to make more videos !! ❤️✌️
@@TheAdityaVerma Bhaiya ..in desperate need of a playlist on Recursion..!! Love your work
Make video on dp for grid
i switched to your next video but suddenly i realised that i need to say thanku for your amazing explanation and great efforts.
Move on
lol.
Abdul Bari is a great person.
@@llliiilll3624 Ya Abdul Bari is great but not as great as him
Rachit's boasts justifies too : /
Well Gaurav sen doesn't boasts
I usually don't hit like button on much videos,but you have to hit like in all his videos,they all are so good
THIS VIDEO SHOULD BE RE-TITLED AS "BOTTOM UP APPROACH" WHICH IS TABULATION.
This was what I too was wondering as this is Bottom up approach as the subproblems are solved first and then we go to the top to solve the main problem.
Here Bottom Up Approach ko sikha ke , he has tried to explain that top down mein bhi vahi kara ja sakta hai .And this is top down only.
Hatsoff to your coding experience and joting down points to convert one method to another. Thanks for sharing these points.
I am one of those jinka "recursion hi strong nai h"
bhai karte rahe kosish geeks for geeks se backtracking ke questions kar...confidence aane lagega
Bro aditya bhaiya ki recursion playlist dekhlo fhir aapko for loop bekar lagne lag jayega
@@shubhamrana412 feeling same bhai
@@shubhamrana412 Lekin using for loop is better than using recursion.
@@sonulohani using a loop can be efficient? Btw what is the time complexity of the recursive function does it depend on the recurrence relation?
We don't watch videos here in channel, We watch playlists..Amazing content...
Recursion seekhlo DP Halwa lagegi
.
.
.
edit: ye kon bc dislike kar ra he
Finally, after 36 minutes, my anxiety of changing n,w -> I, j ended. Through out the video while you were writing the code for iterative I was like "Bhai i,j hoga .. n,w nahi !!! ". Although, I trusted you enough to watch the complete video and then you said.. "Saare n, w ko i, j me badal denge"... Anxiety Ended!
Today I got selected in Flipkart all because of your videos Aditya!
Besides learning technical stuff, I got to learn from you on how to handle and approach complex problems.
Thanks a lot!
I really owe you a lot, can't msg on LinkedIn since you haven't accepted my request but I'm gonna ping you as soon as I join to thank you :)
I have nothing different to say!Commenting just so the dumb youtube algorithm can see this gem and start suggesting. I was trying to learn knapsack and accidently found your playlist comment at the corner of famous video where people were struggling to understand the concept. I was skeptical and almost skipped seeing the video is in Hindi since my hindi is not so great. Somehow i watched the first one and now i am in love with this. You are such an awesome teacher , please keep doing this. Much Love.
Engrave this in stones and history will witness that best ever tutorials created for Dynamic Programming on entire planet was created by Aditya Verma. Period.
The best explanation of dp, Now I again have some confidence.
I saw tons of video dp but this is the best.
By far the best video on programming foundation for DP on RUclips or any other educational site. You got an unique and excellent way of expressing complex concepts with simplicity. I hope you will create more videos.
He is teaching like he really cares for us... That line "bas tum recursive function acche se likh do mere bhai 🤍 20:40"
ur explanation is so well that even before seeing this video .. and understanding how DP works , i have solved 20 DP leetcode problems nd i am continuing series now .!
An elder brother holding the hand of his younger brother and introducing the world of Dynamic Programming. ❤
The beauty of your explaination is it gave me a feel as I myself have solved and analyzed the approach and solution of the problem. This is one of the best youtube videos i have ever watched!!!!!!!!!!!!!!!!!thanks keep uploading.............
do doubt one of the best teacher i am confuse in between how to convert recursive code to tabulation and you made it very simple
thank you dp King.....
Thnku so much bhai🙏🙏. U have made dynamic programming as the easiest topic for us. Ur teaching style is amazing 👍👍👍👍
Bhai khatarnaak, kya insight di hai..Thank god for utube and thankgod for u.
Your videos are very helpful .
Your promise is true that no one on RUclips teach us like you .
Thanks a lot sir .make more videos on data structure and algorithms it will be helpful for students .♥️♥️
This explanation is tremendous . I wish I had found this earlier!!!.Please post more and more videos!!!!
Hey, very good and in-depth explanation. You seriously took 4 long videos to come to 0/1 knapsack tabulation solution. And to my surprise, they were very much helpful in understanding the concepts. It increases my base interest in dynamic programming. I must say that. Now I understand what lookup table means(used everywhere) that I previously used to confuse a lot in memoization. Thanks a lot!!!
Just one suggestion, you please mention in the Introduction and in the Title of this video that it is bottom up approach(Tabulation) not top-down DP. No need to make another video or edit any videos. :D
What the hell!! This is damn. I prepared for gate and just memorized the approach for different DP problem but from your explanation, I am to understand it thoroughly.. Bhai OP