DP 19. 0/1 Knapsack | Recursion to Single Array Space Optimised Approach | DP on Subsequences
Вставка
- Опубліковано 29 чер 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
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
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
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.
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
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) .
UNDERSTOOD!! that single array space optimization is mind blowing!!...really loved it! THANK YOU SOOO MUCH
this is the easiest ever explanation of 0/1 knapsack. Godly insane man!!!
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] ?
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
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] ?
Single row optimization was really a god tier stuff... ⚡
Thank you and UNDERSTOOD
Loved the Single Array space optimised approach !!
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............🙂🙏
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!!!
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
Even in the most common problem, Striver teaches something new, thankyou so much Raj Bhaiya!
single array technique was mind blowing concept ... thank u striver
Thanks striver! Watched the dp lecture in series. Was able to come up with recursion , tabulation and space optimization into 1D all by myself!
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
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
was never able to understand how single array space optimisation works excellent explanation striver. Really helpful!!
Unbelievable that you optimize the code this much. Really you are an extraordinary person. I understood it very clearly. Thank you striver.
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.
The single vector optimization was wonderful 🔥😅
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.
UNDERSTOOD.. !
wooooooahhh that last space optimization climax gonna enlighten your brain nerves...
Thanks striver for the video... :)
Great video. First time I am able to understand tabulation and space optimization intuitively.
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] ?
US sir .. Love the single array optimization....keep going sir.
why in tabulation base condition is from i=w[0] ?
Loved the single array optimisation. U r doing a brilliant job. Thanks a ton!!!
This is one of the best explanations of this question and the space optimization is just amazing. Thanks striver
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] ?
Awesome, seriously love the last 1d optimization.
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
Python solutions for 0/1 knapsack
0/1 knapsack top down recursive: pastebin.com/t1Q6fZ9N
0/1 knapsack 2D DP memoization: pastebin.com/QwphY5r2
0/1 knapsack 1D DP(space-optimized): pastebin.com/WiGceGdt
1D Array optimisation is really Awesome 🔥❤
why in tabulation base condition is from i=w[0] ?
What a amazing series i am able to do question on my own
why in tabulation base condition is from i=w[0] ?
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] ?
I was able to write top down approach on my own. It's all because of the previous lectures. Thanks to you brother.
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] ?
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
It was amazing !!! I was trying it by myself but couldn't do the optimization in one Single Array, but now Understood !!!
Absolutely loved the idea of space optimization to a single array. Understood !
POV : Educated guys do not steal 💀💀
UNDERSTOOD............one row optimization is an amazing thing.........Thank You So Much Striver Bhaiya for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood, had to write it out to understand the tabulation logic but that made both space optimization a lot easier to understand.
1D Array approach was mind-blowing !!
As always, thanks for the great lecture !!
No doubt why you are most loved teacher !! HATS OFF. ---> one array space optimization was something out of the box
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] ?
Your effort for optimization as tremendous . I have no word to praise and respect you .
Salute you sri.
Understood !! The single array optimization was mind-blowing.
Really the space optimization using only a single row was wow, which I realised after dry running of course!
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!!!!!!!...Thanqew so much Striver u made concepts easy......space optimization with 1array was incredible💫
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] ?
Awesome bro. Such UA-camrs like you and other also are support for us. Thanks for your every video.
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] ?
Best explanation.Just loved it Thanks a lot striver for making such series .✌✌
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] ?
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 !
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.
loved your one array optimization technique❤❤
really amazing video didnt find such video anywhere else
Understood! Space optimization is mind blowing🤯🤯
Amazed by the one-dimesional spaced optimzation
yes, 1d array optimization technique was amazing!!
Underrrrrrssstttttooood now seeing the length of string u can guess how much I loved this thnx man..
LOVED THE 1 ARRAY SPACE OPTIMIZATION.
Understood ❤. The 1 array space optimization part was amazing, it unlocked one more part of my brain.😅
The best ever explaination of DP present on Earth is yours.
Understood, last optimisation was awesome👏
Thank you striver. Solved by myself in Tabulization and memoization and space optimzation❣
Wonderful, Knapsack was never this easy before 🤩
35:54 LOL
Awesome walk through to the intuition for optimizations.. thanks striver
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] ?
It was just mind-blowing👏.
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] ?
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 😁
Totally loved the one array optimisation.
Gazab bhai, understood, only this video explains this single array approach that too so succinctly
Best series on UA-cam hands down , keep it going bhaiya🤞
Understood Bhaiya
Understood and love it striver. Thank you for this wonderful content.
Amazing work bhai .. understood so complex problems so easily.
Loved the one array approach
I have seen so many DP series, but boy oh boy your videos are next level thank you so much Raj bhaiya
Thanku for this amazing series. And as always #UNDERSTOOD.
Understood Sir👍. Optimization using single array was just amazing !!!
You content is so so good. Understood very well.
Liked the space optimization at the end. Loving it.
Amazing space optimization ever seen in Dynamic programming, these type of lectures motivates us to work hard, Thanks bro
Incredible explanation as always! Thank you, Stiver :)
why in tabulation base condition is from i=w[0] ?
Cool Loved the last optimization.🔥
Striver, that's super cool logic for using a single row✨
just absolutely insane! the concept that we don't need to use the right ones 👌
Amazing Explanation -understood the single row optimisation -Thanks Striver
Understood!!!🔥🔥🔥🔥🔥 one row space optimisation is very very awesome and very very great.