DP 23. Unbounded Knapsack | 1-D Array Space Optimised Approach
HTML-код
- Опубликовано: 20 окт 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...
![FNAF vs TF2 - Episode 2 [SFM]](http://i.ytimg.com/vi/z5b3V2-VLb0/mqdefault.jpg)
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!!
🙌👏👏
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]
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!
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! 💯
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 +++✌️
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.❤❤❤❤❤
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.
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
Hey Striver, I solved the problem without watching the video. All credit goes to you, Thank you so much.
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 ..
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🙏🙏♥♥
Solved the problem without watching the video.
Thank you for the knowledge you are providing.
understood, done the problem from recursion to tabulation with space optimization by myself..... very thankful for this dp playlist.
If someone is wondering why we iterate in forward manner in inner loop in unbounded knapsack while 1-d array optimization, and in reverse order in bounded knapsack, just remember this rule of thumb
For bounded knapsack problems (each item can only be used once), reverse iteration is important to avoid reusing the same item.
For unbounded knapsack problems (items can be reused), forward iteration ensures you're considering the possibility of reusing the same item multiple times within the same loop
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.
I Solved By my own till 2 array space optimization,..Thanks a lot for the awesome quality content #UNDERSTOOD
Only RUclipsr who will teach you in way so that you think on your own and solve it without watching his video. No Words !💯
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 !!
thank you so much striver, my understanding has improved so much watching these video. may god bless you.
Thanks, solved using all the 3 approach without watching this video.
Great dp series
You actually made dp easy now I only need to think of recursion and that's it🌝
Best DP series in all RUclips.
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.
i done it my own although it was based on preveous problems but this shows you are getting ready for new preblems too.
Thank you so much striver, i solved the problem using all 3 approaches without watching the video. I didn't think that i had it in me to do it but hey, i did it. 😭😭
Superb.. last level of space optimization!!
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.😄😄
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
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 !
I was able to do it and do no believe it myself. thank you so much.
Base case i
Solved before watching the video.. you have made dp easy for me :) Thank you
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"
was able to solve at one go.
Well done Striver
Thanks alot striver, I have completed the problem on my own. Thanks alot!
1d array approach is super wonderful 😊😊😊😊
understood and did till space optimization on my own
missed
bhaiya content bohot acha hai apka. i am really enjoying it. thanks for this
understood bhaiya! i solved this problem all three approch without watching this vedio.
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!!
Thankyou for great explanation striver
Awesome content in this series! Thank you and Understood ♥
Understood, did all and even space optimization to 1 1d array before watching video
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!
I done it by my self , all thanks goes to striver 😁😁
Understood, sir. Thank you very much.
Understood. Kudos to you for the amazing job! Can you make a playlist on Array problems too?
UNDERSTOOD... !
Thanks striver for the video... :)
understood , amazing explanation, sets clearly in the mind
Solved by myself all memoization, tabulation and space optimization done.😀😀
Understood ❤
Bhaiya recursion to space optimisation khud likha pura ❤️❤️❤️
striver....u are like a gem for us🥺☺
Here why are we using overidden values from the left ? unlike in knapsack problem where we went from the right
Understood!! Thank you very very VERY MUCH!!!
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.
Awesome explanation...
Understood...Completed (23/56)
understood
us...and also submitted the question in all the approaches by myself
3 days ago: DP is one of my weekest topics, i fear it to death.
DP-1: OK, LET'S DO THIS.
DP-15-17 I think I'm getting a hang of it.
DP-20s Can DO IT MYSELF NOW..
bye, i'm going to understand all the remaining patterns ahead.
and also, Understood.
Instead of pick to be zero cant we keep int_ min or -1e9 as we were finding the max element
Understood,able to solve by myself till 2 array space optimization
Hey, Striver
I solved it on my own, So It is working for this base case also. Given below
why it is working in this case
if ind == 0:
if W % weights[ind] == 0:
return (W // weights[ind]) * values[ind]
return 0
instead of
if ind == 0:
return (W // weights[ind]) * values[ind]
Why it is like that?
the 1-D array part was so good.
UNderstood.
Striver I think Recursion Worst Space Complexity without the DP array will be O(W + IND) , consider our n-1th index value is 1 and its wt is also 1 and our bag weight is 10 then by logic of standing at the same index first we will go till O(W) stack space and then all the non takes will kick in and we will go till ind == 0 which gives us O(IND) so space complexity will be O(W+IND)
Thanks Striver. Understood. Learnt a lot.
UNDERSTOOD....
Thank you striver
understood☺
understood , Thanks striver
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?
thanks for this awesome content
understood very well
Continue from 18:00
Smartest thing on the planet ❣
Shouldn't we traverse the prev array from right to left as the current value is dependent on previous values which keep changing if we traverse from left to right in the single array approach?? You did that in the 0-1 knapsack problem.
I am thinking the same
Understood! Just wow 😲
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
thnx, was able to do this by myself
Understood Striver!!!Thank you for the amazing content
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🙏🙏
solved it by myself. Thank you striver.
Understood Sir, Thank you very much
understood :)❤
thank you very much striver i have solved this sum by my own
understood !!!
can you please tell me, do we really need to space optimize to a 1-d solution during the interview or it is optional?
base case for tabulation should be for (int i = 0; i
UNDERSTOOD!!!!
AND LOVED IT!!
Thanks striver, was able to do it in all four ways by myself after sincerely following your playlist. ❤
UNDERSTOOD BABY!
Very well explained!!
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
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
Understood Thanks You Striver 😍
Wow 🔥🔥
Bhaiya, How many videos will be there in total?
buying vegetables is the variation of ninjas training on gfg