DP 23. Unbounded Knapsack | 1-D Array Space Optimised Approach
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3IvPdXS
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the problem of minimum coins. We start with memoization, then tabulation, then two-row space optimization. This problem is the seventh problem on DP on Subsequences Pattern. Please watch DP 14 before watching this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
Hey Striver, I solved the problem in all 3 approaches without watching the video. All credit goes to you, Thanks a lot. You are the best.
Same. Striver is magical.
Same bro I also solved 3 approaches without watching.
bro what r you doing write now ? means professionally ?
@@udaypratapsingh8923YES
@@anuragpandey8165 YUP
STRIVER! I solved the whole problem in recursion, memoization, tabulation, Space optimization and then even the 1D Array ALL ALONEEE!!
Thank youuuu! YOU ARE THE BEST TEACHER!!
🙌👏👏
best thing about him is , rather than teaching how to simply solve ,he teaches us how to think , which makes us solve on our own ! GOD level!
Even befor you explained the question just by name of topic i got the que what we gona do and i smiled like just 10 days ago i was suffering from DP and now i can predict what the que gonna be 😌Thanks Stiver Respect +++✌️
For someone finding Recursive + memoised, tabulated, space optimised approaches:
My flow of solving the dp is opposite to that of what Raj bhai do, (I prefer starting index from 0---> n-1) so accordingly, down below are my approaches:
#include
int helper(int ind, int capacity,vector &profit, vector &weight, int n, vector &memo){
if(ind>=n) return -1e9;
if(capacity==0) return 0;
if(memo[ind][capacity]!=-1) return memo[ind][capacity];
// take, nottake
int take=0, nottake=0;
if(weight[ind]
1-D Array Approach was amazing. Thank You
why didnt we do from right to left ? the iteration
@@lakshsinghania Because we need the current guy’s backward data and not previous guy’s
Whhoooaa striver, excellent concept.
Without seeing the solution, I am able to solve it with all approaches, all credit goes to you sirji.
Hey Striver, I solved the problem in all 3 approaches without watching the video. All credit goes to you, Thanks a lot. You are the best.
Understood! Since you've already explained these concepts so well in the previous problem, I was able to solve it on my own. Thanks, Striver! 💯
Hey Striver, I solved the problem in all 3 approaches without watching the video. All credit goes to you, Thanks a lot. You are the best.❤❤❤❤❤
Hey Striver, I solved the problem without watching the video. All credit goes to you, Thank you so much.
Hey striver, I have been watching your videos since very long and especially this playlist has helped me overcome the fear of dp.....thanks a lot🙏🙏♥♥
I Solved By my own till 2 array space optimization,..Thanks a lot for the awesome quality content #UNDERSTOOD
understood, done the problem from recursion to tabulation with space optimization by myself..... very thankful for this dp playlist.
You actually made dp easy now I only need to think of recursion and that's it🌝
Only TH-camr who will teach you in way so that you think on your own and solve it without watching his video. No Words !💯
Thanks, solved using all the 3 approach without watching this video.
Great dp series
From not solving to any problem using Tabulation to Solving at first go, thanks for In-depth DP video!!
Understood !! hey striver i solved the problem on my own, feels amazing, keep going , keep growing !!
Solved the problem without watching the video.
Thank you for the knowledge you are providing.
i solved this problem in all approach recursion >>>>> memo>>>> tabulation >>>>> space optimization[ 2 * 1d array] >>>>>> space optimization[1d array]
without watching the video..
thank you so much ...
you are amazing teacher ..
I followed this series from first videos and at this stage.I did this question in 11:44 min without watching this video. Thanks bro for your efforts to make such playlist.
Understood😃 and please make some videos where we can't use 2D Vector ,i.e. we need hashmaps to store them becoz I'm facing problem on that kind of qs.
Your contents are the best👌👌.
Thank you
Solved by myself all memoization, tabulation and space optimization done.😀😀
i done it my own although it was based on preveous problems but this shows you are getting ready for new preblems too.
Following this series from first video and Solved this question without watching the video. (I would not have solved any problem in last month same date but now I can solve basic and medium level dp problem). Thanks to striver.
Best DP series in all TH-cam.
Thanks alot striver, I have completed the problem on my own. Thanks alot!
I done it by my self , all thanks goes to striver 😁😁
Understood, sir. Thank you very much.
Understood, did all and even space optimization to 1 1d array before watching video
thank you so much striver, my understanding has improved so much watching these video. may god bless you.
Superb.. last level of space optimization!!
understood and did till space optimization on my own
missed
UNDERSTOOD... !
Thanks striver for the video... :)
hello striver solved this question in all approaches except the tabulation one got confused of base case but i was close to exactly what you have done in this video. that means i'm learning great thanks for this wonderfull playlist.
i get you bro u must not start your base case for loop from weight [0] to w+1
instead u start it from 0 to w+1;
same happen here!!
I was able to do it and do no believe it myself. thank you so much.
understood but i did this before watching the video to test whether i am able to solve. You have made us think on our own Thanks Striver.😄😄
I am not understanding why we are not traversing for capacity from back for 1D space optimization as for cur index we need prev index values and cur array prev values so why not from back traverse
I got till memoization but made small mistake in tabulation, thankyou for teaching so well !
Was able to solve all 4 approaches without seeing the video, although was very delighted to watch the space optimization.
Thank you bhaiya for making dp so easy:))
"Understood"
Understood. Kudos to you for the amazing job! Can you make a playlist on Array problems too?
Thankyou for great explanation striver
was able to solve at one go.
Well done Striver
Solved before watching the video.. you have made dp easy for me :) Thank you
Base case i
Can anyone explain why left to right (W=0 to maxWeight) does not work in 01 knapsack, but it does work in unbounded knapsack. I am very confused they look similar to me. Please help!
bro u got ans?
Understood...Completed (23/56)
bhaiya content bohot acha hai apka. i am really enjoying it. thanks for this
Why the forwoard iteration of wieght for using 1-d array not causing any problem?like dp 19
Because we need the current guy’s backward data and not previous guy’s
@@takeUforward in 19 th also we wanted curr guys backward na so why error there
@@sushant8686 in 19 , we were no in the same index after taking a particular element , consider the following statement of taking a particular element of dp 19 and this video :-
dp 19:
take = value[ind]+help(ind-1,w-weight[ind],weight,value,dp);
dp 23:
take = profit[ind]+help(ind,w-weight[ind],profit,weight,dp);
in case of dp 19 , we are going to ind-1 , and for that , in our tabulation code , we will use prev array , in case of dp 23 we are in same index , and in our tabulation code , we will use curr array , if we are using curr , we do not need to worry about prev[w-weight[ind]], that is why forward iteration will work here .
@@abhimanyusingh6445 thanks bhai you have cleared my doubt🙏🙏
striver....u are like a gem for us🥺☺
understood bhaiya! i solved this problem all three approch without watching this vedio.
1d array approach is super wonderful 😊😊😊😊
understood , amazing explanation, sets clearly in the mind
Awesome content in this series! Thank you and Understood ♥
Awesome explanation...
hey striver finally i am being to solve this without watching the solutions a;ll thanks to you man ❤❤ and a Big "Understood".
Understood!! Thank you very very VERY MUCH!!!
Understood ❤
This was the video which solidified my understanding in DP from all the concepts learnt in the previous videos. thank you so much Striver Bhaiya! Understood not only this video but the previous videos clearly!
Understood! Just wow 😲
Bhaiya recursion to space optimisation khud likha pura ❤️❤️❤️
Striver, we need problem where we can't use 2D grid , we have to use hashmaps for memo...
how are those different? maybe we should be able to solve them using maps to store. Or am i missing something?
@@mikelan9854 I guess the approach will be same just converting the 2d variables in form of string and storing it
@@thinkingmad1685 2d array is efficient as using map might give tle some times
us...and also submitted the question in all the approaches by myself
Thanks Striver. Understood. Learnt a lot.
Smartest thing on the planet ❣
the 1-D array part was so good.
UNderstood.
UNDERSTOOD....
Thank you striver
Understood Striver!!!Thank you for the amazing content
thnx, was able to do this by myself
UNDERSTOOD BABY!
Continue from 18:00
solved it by myself. Thank you striver.
understood , Thanks striver
understood ,thanks alot
Thank U striver.
Understood,able to solve by myself till 2 array space optimization
Understood!!
Thanks!
Understood Sir, Thank you very much
Understood sir !🙏🙏
Bhaiya ,why are we not writing the base case for weight parameter here ? how will the Take call terminate as the index is not decreasing , the weight is ,but there is no base case for weight ?
we don't have base case for that but we do have restriction for recursion call , that is when bag weight is less than the weight of item we will stop taking items and for that particular call take will be zero
Make recursion tree to understand more....
thanks for asking this . I also have same doubt
thank you very much striver i have solved this sum by my own
understood☺
understood, but I solved this problem myself without seeing the solution upto 2 array space optimization. Needed the video to realize further optimization to a single array.
UNDERSTOOD!!!!
AND LOVED IT!!
Thanks striver, was able to do it in all four ways by myself after sincerely following your playlist. ❤
Here why are we using overidden values from the left ? unlike in knapsack problem where we went from the right
Question: How does the tabulation cover the case of picking multiple elements?
bro u use dp[i][t-weight[i]] in pick case
and in not pick use dp[i-1][t];
and if you want to know working watch old videos in which striver sir explain it deeply
or dry run for small values you get it easily and never forget then if you DIY
understood very well
Very well explained!!
Amazing bahot Achha padhate ho ❤️❤️
aap kyuun padh rhi ho didi
Understood Thanks You Striver 😍
Understood bhaiyya!
Understood, thanks!
buying vegetables is the variation of ninjas training on gfg
understood :)❤
hey striver, at 13:27 why didnt we write this condition statement in the base case
if(wt[0]
Look We can do it like this as well
if(ind == 0){
if(weight[0]
Observe that Even if you won't write the condition if(weight[0] maxWeight then (maxWeight/weight[0]) is always going to be 0. Hence this case is automatically handled ! Hope this helps.
but why adding that statement is giving wrong answer , it should pass all the test cases no ?i am trying to figure this out for so long😭😭😭😭@@ObitoXuchiha942
@@ObitoXuchiha942 aite got it! ik its 1 yr later xd but got it that time. just revising the stuffs
Thanks a Lot Striver🤩
Understoood sir!!
Understood 🎉