DP 19. 0/1 Knapsack | Recursion to Single Array Space Optimised Approach | DP on Subsequences
ฝัง
- เผยแพร่เมื่อ 20 ก.ค. 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3KHpP3v
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of 0/1 Knapsack. We start with memoization, then tabulation, then two-row space optimization, then single row optimisation. This problem is the fifth problem on DP on Subsequences Pattern. Please watch DP 17 before watching this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
![[TH] 2024 PMWC x EWC Group Stage Day 2 | PUBG MOBILE WORLD CUP x ESPORTS WORLD CUP](http://i.ytimg.com/vi/vwIQyCmNIBU/mqdefault.jpg)
I need your support, and you can do that by giving me alike, and commenting "understood" if I was able to explain you. The single space thing can be applied to all the subset-sum problems as well.
Keeping a like target of 500 ❤✌🏼
one of the doubt i am getting how are u converting the base case of memorized code to tablar dp
like in this case
if(indx==0)
{
if(wt[0]
can we take the starting value of take as -1 ??
@@mdmurtaza8321 The dp is declared as dp[n][W+1]. In this base case we are trying(to handle index = 0 condition, i.e. 0th row on dp matrix) to fill dp[0][0 to maxWeight] so that filling dp for every weight till maxWeight. The for loop is starting with wt[0] because, the base condition is for 0th index i.e. 0th index wt[0] and we have minimum weight at 0th index, the thief can steal whatever element is there on index = 0 until weight of the element is less or equal to maxWeight (wt[0] to maxWeight) .
I checked the like count has crossed ever 7000😎
understood
Understood :)
Can't believe that I was able to solve one of the most famous problems out there on my first atttempt, completely on my own. You may never see this comment Striver, but this playlist is genuinely incredible, so thank you *sooooo* much for putting this incredible content out there, all for free.
You are one of the most intelligent people I have ever seen. Not finished watching till end, just wanted to tell you. You make me feel I am intelligent too. Thanks @striver.
u r right btw : )
@@udaypratapsingh8923 ok bhay
Haven see a lot of DP videos, and mostly all of them write the space optimized code including the 1-D array, but not teaches exactly why they wrote it that way. Striver bro great teaching and energy, loved it
space optimization to just 1D array was insane 🤯
why in tabulation base condition is from i=w[0] ?
@@MadhavGupta-fi2tu Compare it to the base condition in the recursive solution. We can add wt[0] our knapsack only if its value is less than the target w, so for the index i = 0, we simply looped over all values from wt[0] to the target value w.
@@MadhavGupta-fi2tu because for i < w[0], dp[0][i] is 0, which is already pre filled at time of vector declaration
because, suppose that we landed at index=0, with the bag capacity still having >= weight[0], then we can definitely place the item which is at index 0 into the bag. So, for all the values of bag capacity>=weight[0], the value that we can return is value[0].
@@MadhavGupta-fi2tu //Base case - for all wieghts more than maxWeight at zero index will return value else return 0
Mind Blowing Observation for that space optimization, things like these define the difference between a googler and any other person, lot's to learn from you, Striver, in terms of education as well as life lessons. As always, Understood!
bruh u just made google sound like iit
Understood, I am following this series. I have gone through a few of other playlists but this one is my constant now. Learning each day. You literally mad DP very easy to grasp now. Thank you sir.
why in tabulation base condition is from i=w[0] ?
@@MadhavGupta-fi2tu The for loop is starting with wt[0] because, the base condition is for 0th index i.e. 0th index wt[0] and we have minimum weight at 0th index, the thief can steal whatever element is there on index = 0 until weight of the element is less or equal to maxWeight (wt[0] to maxWeight) .
Hey i am learning dev from harkirat wanna ask how to start dsa journey will you please guide me
The way striver say "WHAT ARE YOU WAITING FOR?" always motivates me more and fills more energy into me..!! Thanks a lot striver.
I saw so many articles which used just a single array for space optimization and was never able to understand it. Everybody had given vague answers about this and I had literally scouted the entire internet for this explanation. And today I am finally able to understand it. Thank you so much Striver bhaiya. There is no match of you 🙏🙏🙏
so True
why in tabulation base condition is from i=w[0] ?
Thanks, sir, without seeing this video I can do recursive, recursive with memoization, tabulation and space optimization with two arrays by learning last 18 lectures, and now I can do the one array optimization. This DP series has helped me solve questions easily that I can't previously. Once again Thank you for bringing this amazing DP series. LOVE your work. And Lastly UNDERSTOOD!!❤❤
why in tabulation base condition is from i=w[0] ?
@@MadhavGupta-fi2tu Because it is from that index that the item at index 0 can be picked up, before that the maximum weight that we can hold will be lesser than the weight of item 0
Every single time you amaze me Raj!!! Hats off to your hardwork man!! Big Salute. And most importantly very grateful to be having taught by you!!!!!!
UNDERSTOOD!! that single array space optimization is mind blowing!!...really loved it! THANK YOU SOOO MUCH
Even in the most common problem, Striver teaches something new, thankyou so much Raj Bhaiya!
I never thought I could be able to solve DP problems all by myself, but just a moment ago I did!!!! Thank you striver, You're amazing.
why in tabulation base condition is from i=w[0] ?
@@MadhavGupta-fi2tu because you are going from n-1 to 0, so in the last case you have one item left to steal which is basically the 0th item
At the end of the video space optimisation you told me i was doing the same way in previous questions when i figured it out myself that if we are using previous element of previous array then why dont we traverse backward and compute and store there in that previous array. Now you did it and now i am sure about the optimisation i was thinking.
I bet that I Understood............🙂🙏
Unbelievable that you optimize the code this much. Really you are an extraordinary person. I understood it very clearly. Thank you striver.
Single row optimization was really a god tier stuff... ⚡
Thank you and UNDERSTOOD
Understood kaka
The optimisation into a single vector was mind blowing!
You clearly deserve Google Warsaw!
it is already in geeks for geeks if you havent seen this before dude nothing out of the moon
why in tabulation base condition is from i=w[0] ?
@@karthikeyan1996_ zyada mat bol Adress bata apna pilna h to
Thanks striver! Watched the dp lecture in series. Was able to come up with recursion , tabulation and space optimization into 1D all by myself!
Hi striver! You are really an amazing person and best mentor we could have asked for, i can't tell you how much gratitude I have for you.
Once again Understood!!!
You are travelling a whole journey from recursion-> memorization -> Space Optimisation that is amazing. No one else explain like that 🦾💪💪
Aditya Verma also explained in same way and in depth also
Tabulation also 🔥
@@jiteshkhatri2896 who's is best at teaching everything briefly in your pov ?
@@jeevaalok1467 if u want can share any social media handle where we can discuss.
@@jeevaalok1467Both are of the same standards, but I chose a striver from Aditya verma becoz I can't understand Hindi.
Loved the Single Array space optimised approach !!
First of all thank you for the series. I believe the base cases from the previous and this video are un necessarily complicated. You can just check if(idx < 0 || w == 0) { return 0;}, we don't have to make 0 as a special case and write confusing base cases (if else's). once the index 0 is processed like rest of the others indexes, it should stop. I hope you take it as a constructive criticism!☮
That's right if we only had to do rec and memoization, but in tabulation how will u initialize negastive index?? Ik it can be done, but then memo to tabu step will involve some extra work which is avoided if we do this way, also why will the fn have to handle a negative index in the first place?? it will never occur, idx is always >=0, in yr case it is becoming
@@SJ_46 why we didn't write when
if(W==0)
return 0;
@@cse048harshkumawat6 did u find the answer because I am thinking the same?
@@amansaxena5620 @CSE048 Harsh Kumawat we are only taking particular element if it is less than or equal to W, So even if it becomes 0 in between, then we will keep moving towards base case, i.e. F(idx-1, W) => Eventually it will go in Base condition, and it will be handled there.
DP used to be a nightmare, I sort of ran away from it but after following your playlist it seems something approachable. I am soo happy I am able to solve these on my own.
this is the easiest ever explanation of 0/1 knapsack. Godly insane man!!!
Great Series BHAIYA. You are doing a great job. Gradually now I am able to build logic and write the code on my own. #UNDERSTOOD
US sir .. Love the single array optimization....keep going sir.
why in tabulation base condition is from i=w[0] ?
I could solve the recursive, memoisation, tabulation and space optimisation approach with 2 vectors on my own.. So thankful to you striver. The last space optimised method was very nice. Understood and a big big thank you :)
Understood , solved all recursive , memoization , tabulation and space optimization by myself .
The single vector optimization was wonderful 🔥😅
From fearing from "DP" to solve question by my own without watching your solution, it's a great journey! BTW damn good observation to optimize it into single array! grateful ♥
why in tabulation base condition is from i=w[0] ?
single array technique was mind blowing concept ... thank u striver
was never able to understand how single array space optimisation works excellent explanation striver. Really helpful!!
Understood Bro. The single array optimization was awesome . It showed the power keen observation 💥💥. Hope one day , I achieve such an observation skill. Thanks for the video bro. Keep the DP series going 💪💪.
This is like my personal wish , i would like to see some DP problems based on subarrays in this series , because i find it hard differentiating it from subsequence problems. I believe only you can make me understand. Pls consider this bro.
why in tabulation base condition is from i=w[0] ?
Awesome, seriously love the last 1d optimization.
why in tabulation base condition is from i=w[0] ?
All are born to go forward
And then there is you, who was born to take us forward
Living legend
Striver sir...🙇🙇
Loved the single array optimisation. U r doing a brilliant job. Thanks a ton!!!
What a amazing series i am able to do question on my own
why in tabulation base condition is from i=w[0] ?
1D Array optimisation is really Awesome 🔥❤
why in tabulation base condition is from i=w[0] ?
Hello Sir this question seems to be a very simple and direct one when read for the first time if you have basic idea about DP on subsequences. But when you code it and visualise using the 2D DP array / matrix and check the test cases, only then one is blown away by the beauty of it. Also the manner how the previous Row is enough to evaluate maximum value adds to the class and excellence of the question !
This is one of the best explanations of this question and the space optimization is just amazing. Thanks striver
Those who thought of using greedy by sorting according to (val/wt),
Test Case: wt-> 3 2 4
bag=5 val->57 36 80
greedy gives=) 80 , while ans=93
That was fractional knapsack
@@avirupmazumder4840 In fractional knapsack we break items, but as you can see here we didn't break the item if we had broken items then greedy would have give (80 + 19) => 99
thanks...was confused@@codermal
Bhaiya one suggestion can you please consider making a video on coin change type problems because it gets confusing when all the permutations are counted and in some only unique ones are counted.
why in tabulation base condition is from i=w[0] ?
No doubt why you are most loved teacher !! HATS OFF. ---> one array space optimization was something out of the box
I was able to write top down approach on my own. It's all because of the previous lectures. Thanks to you brother.
POV : Educated guys do not steal 💀💀
understood, had to write it out to understand the tabulation logic but that made both space optimization a lot easier to understand.
UNDERSTOOD.. !
wooooooahhh that last space optimization climax gonna enlighten your brain nerves...
Thanks striver for the video... :)
It was amazing !!! I was trying it by myself but couldn't do the optimization in one Single Array, but now Understood !!!
I bet no one in the entire you tube teaching community can match your style of teaching and applying brain. Last part of space optimization really blew my mind.. Hats off Sir!!
why in tabulation base condition is from i=w[0] ?
UNDERSTOOD............one row optimization is an amazing thing.........Thank You So Much Striver Bhaiya for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
My love for this series getting deeper everyday,
thanks for for the last optimization, its amazing
why in tabulation base condition is from i=w[0] ?
Really the space optimization using only a single row was wow, which I realised after dry running of course!
1D Array approach was mind-blowing !!
As always, thanks for the great lecture !!
Your effort for optimization as tremendous . I have no word to praise and respect you .
Salute you sri.
One array optimization is just next level thing. This shows how deep you understand,exactly what previous values our code is using while computing our present value.This is only visible if we manually do a dry run in tabular form .
why in tabulation base condition is from i=w[0] ?
Great video. First time I am able to understand tabulation and space optimization intuitively.
understood! you are an extra ordinary teacher and make everything doable for us as well. thank you so much
Simplest explanation ever , and the way you had arranged the DP problems is really outstanding its makes every problem so simple. Thankyou 😊
why in tabulation base condition is from i=w[0] ?
the last concept was just like a thrilling and amazing part , love you striver.....soon we will meet
Absolutely loved the idea of space optimization to a single array. Understood !
Understood!!!!!!!...Thanqew so much Striver u made concepts easy......space optimization with 1array was incredible💫
Mind blowing space optimisation....Hats Off Bhaiya!!!! Understood!
Man that lecture was amazing from start to end ! The final space optimization that really was like icing on the cake ! Thanks striver Understood!
why in tabulation base condition is from i=w[0] ?
Understood !! The single array optimization was mind-blowing.
Hi bro, before starting this series i had zero knowledge in dp and searched for lot of videos bt no one said right pattern, bt u did for space optimization ,tricks and explained why not greedy works?
We will appreciate ur work
Thank you
Learner 😁
Best explanation.Just loved it Thanks a lot striver for making such series .✌✌
This was awesome! No one ever explained when can we go from the other end in loop. This is the best explanation.
why in tabulation base condition is from i=w[0] ?
Wow, Doing this on my own, I knew I have got better. Always assumed knapsack to be very difficult. Now it is a piece of cake. Thank you Striver!
why in tabulation base condition is from i=w[0] ?
Its been a year im learning DSA, Most of the time ive skipped this problem due to awkward expln but now i can't leave it.
Thnxx man😇
why in tabulation base condition is from i=w[0] ?
loved your one array optimization technique❤❤
Striver, that's super cool logic for using a single row✨
Thank you striver. Solved by myself in Tabulization and memoization and space optimzation❣
This is by far the best video that I have watched on 0/1 knapsack...even though I was able to do recursion + memoization as well as 2 row space optimization on my own....this further optimization to one row blew my mind !! AMAZING
Every video on TUF post 2021 will be the best version of all videos you see :P
why in tabulation base condition is from i=w[0] ?
@@MadhavGupta-fi2tu bhai chill kar!! ..kitni lega yaar uski .. itna dhundega tho bhagwan mil jayenge .. thand rakh thodi 😄😄
Awesome bro. Such TH-camrs like you and other also are support for us. Thanks for your every video.
Great Sereies bro. You are doing a great job. Gradually now I am able to build logic and write the code on my own. DP certainly started to look much more easier than before.
Please continue this series and finish it up as quickly as possible. We all are counting on you and we know we will learn a lot from you.
why in tabulation base condition is from i=w[0] ?
@@MadhavGupta-fi2tu if we come to index 0 let's say the the weight there is 5, and the weight
we can take is 3..so we will discard it any value which is lesser than 5
now say if the weight we can take is 9..so from 5 to 9 we populate our dp table with val[0]
Understood ❤. The 1 array space optimization part was amazing, it unlocked one more part of my brain.😅
Underrrrrrssstttttooood now seeing the length of string u can guess how much I loved this thnx man..
In Space Optimization, instead of prev, curr. We can use dp[(ind - 1) % 2]. Where the dp is of size 2 * target.
I have seen so many DP series, but boy oh boy your videos are next level thank you so much Raj bhaiya
35:54 LOL
Awesome walk through to the intuition for optimizations.. thanks striver
Amazed by the one-dimesional spaced optimzation
Amazing space optimization ever seen in Dynamic programming, these type of lectures motivates us to work hard, Thanks bro
yes, 1d array optimization technique was amazing!!
Wonderful, Knapsack was never this easy before 🤩
Understood! Space optimization is mind blowing🤯🤯
The best ever explaination of DP present on Earth is yours.
Understood Bhaiya
Understood and love it striver. Thank you for this wonderful content.
really amazing video didnt find such video anywhere else
Thanku for this amazing series. And as always #UNDERSTOOD.
Gazab bhai, understood, only this video explains this single array approach that too so succinctly
I wish you would take one more state for n so that we can handle case for empty subset with much more ease. i==0 will represent array as empty and for i=1to n, i-1 will represent the index.
Thief sitting and filling the DP table before starting picking up things is real savage !!!! 😁
The best part is,... I always learn something new that I don't learn anywhere else.
What the level of content! Hats off bhaiya for your effort.Thanks you a lot.I am also in the same college of you - JGEC. You are my motivation and spirit of learning coding.
Understood Sir👍. Optimization using single array was just amazing !!!
Amazing Explanation -understood the single row optimisation -Thanks Striver
just absolutely insane! the concept that we don't need to use the right ones 👌
You content is so so good. Understood very well.
I just solved the problem all by myself.. all thanks to you bhaiya!! U r the best teacher i ve seen so far ❤️
why in tabulation base condition is from i=w[0] ?