DP 23. Unbounded Knapsack | 1-D Array Space Optimised Approach

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...

[@sandeeperukulla498]

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.

[@anuragpandey8165]

Same. Striver is magical.

[@surajmisal3898]

Same bro I also solved 3 approaches without watching.

[@udaypratapsingh8923]

bro what r you doing write now ? means professionally ?

[@sagartaak4017]

@@udaypratapsingh8923YES

[@sagartaak4017]

@@anuragpandey8165 YUP

[@GauravThinks]

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]

[@jagannathan1014]

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!

[@tasneemayham974]

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!! 🙌👏👏

[@_Kunal_Pawar]

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! 💯

[@mantrarajgotecha3055]

Whhoooaa striver, excellent concept. Without seeing the solution, I am able to solve it with all approaches, all credit goes to you sirji.

[@sarthakragwan5248]

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 +++✌️

[@GManiKarthik]

Hey Striver, except the last approach of space optimization using 1-D Array, rest I have solved the problem in all the 3 approaches & corresponding time complexities. All credit goes to you man! Thanks a lot. You are the GOAT of DSA. #Understood #DP23 #Hatsoff #Striver

[@nilimsankarbora5911]

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.❤❤❤❤❤

[@shaisthatabassum-f1o]

did it all by myself till space optimization, u explained everything well from the starting, as always understood. BTW am binge watching this playlist

[@thepleasantmoment2705]

Hey Striver, I solved the problem without watching the video. All credit goes to you, Thank you so much.

[@SelvaArumugam-xq5mf]

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.

[@adityarai30]

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🙏🙏♥♥

[@amitkulkarni9682]

Only KZbinr who will teach you in way so that you think on your own and solve it without watching his video. No Words !💯

[@meetharsoda5152]

1-D Array Approach was amazing. Thank You

[@lakshsinghania]

why didnt we do from right to left ? the iteration

[@SujalMahalaha]

@@lakshsinghania Because we need the current guy’s backward data and not previous guy’s

[@Sachin-je7ue]

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.

[@ankishkhandelwal1061]

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 ..

[@NalinTrivedi-b5o]

your way of teaching is just out of the world

[@dipanshusharma9084]

understood, done the problem from recursion to tabulation with space optimization by myself..... very thankful for this dp playlist.

[@himanshuagrawal8012]

I Solved By my own till 2 array space optimization,..Thanks a lot for the awesome quality content #UNDERSTOOD

[@imranimmu4714]

Solved the problem without watching the video. Thank you for the knowledge you are providing.

[@suhaanbhandary4009]

From not solving to any problem using Tabulation to Solving at first go, thanks for In-depth DP video!!

[@MindsetMastery550]

hey sir i have also solved this problem completely without watching this video and in one go thanks a lot for this masterpiece dp series .

[@EliasEH89]

Best DP series in all KZbin.

[@shivammaurya9630]

You actually made dp easy now I only need to think of recursion and that's it🌝

[@surajmisal3898]

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.

[@thebestview8411]

Thank you Striver, I was able to solve the problem(all 3 approaches) with minor hints, thank you

[@OnstreamGaming]

Understood and solved !!! From now I can say that only thing in DP is to write the recurrence --> and rest we can figure it by looking at recurrence--> also have some difficult when dealing with negative numbers in the Tabulation method bottom up.

[@prathamlohia8496]

4/4 at first try without any errors. Thank you Striver.

[@SYCOA12CHAITANYAASOLE]

Understood !! hey striver i solved the problem on my own, feels amazing, keep going , keep growing !!

[@KUMARSAURABH-s5i]

Thanks, solved using all the 3 approach without watching this video. Great dp series

[@KeigoEdits]

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

[@prabhakaran5542]

Understood ❤

[@DevashishJose]

thank you so much striver, my understanding has improved so much watching these video. may god bless you.

[@socify4410]

i done it my own although it was based on preveous problems but this shows you are getting ready for new preblems too.

[@mriduljain6809]

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"

[@ShubhamKumar-fn5be]

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.😄😄

[@cosmiccometyt]

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. 😭😭

[@rushirajparekh9079]

Superb.. last level of space optimization!!

[@princeshubham26]

Solved by myself all memoization, tabulation and space optimization done.😀😀

[@somnathroy102]

I was able to do it and do no believe it myself. thank you so much.

[@anshsaxena7297]

Thanks alot striver, I have completed the problem on my own. Thanks alot!

[@UtkarshWasHereBeforeYou]

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.

[@manishprajapati8544]

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.

[@sagartaak4017]

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!!

[@aliabbas-kj7lm]

was able to solve at one go. Well done Striver

[@DivineVision201]

bhaiya content bohot acha hai apka. i am really enjoying it. thanks for this

[@koushande5679]

Solved before watching the video.. you have made dp easy for me :) Thank you

[@shivkumar-og4ow]

understood bhaiya! i solved this problem all three approch without watching this vedio.

[@RohitKumar-dy2gc]

1d array approach is super wonderful 😊😊😊😊

[@shaktiprasannasahoo7845]

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

[@anmol3749]

Understood Thank you striver⚡

[@dennyage4791]

I done it by my self , all thanks goes to striver 😁😁

[@ketansarode17]

striver....u are like a gem for us🥺☺

[@komalgoel8308]

understood☺

[@aruna5869]

understood :)❤

[@ranasauravsingh]

UNDERSTOOD... ! Thanks striver for the video... :)

[@ntgrn-pr5yx]

UNDERSTOOD , THANK YOU STRIVER

[@MukeshKumar-cc3uh]

Awesome content in this series! Thank you and Understood ♥

[@pranaypatadiya]

Smartest thing on the planet ❣

[@Enigm.1.]

understood

[@morganyu3391]

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!

[@omkarkawatgi]

Base case i

[@Sara-ed3jq]

I got till memoization but made small mistake in tabulation, thankyou for teaching so well !

[@lohitaksha244]

Understood, did all and even space optimization to 1 1d array before watching video

[@ritikshandilya7075]

Thankyou for great explanation striver

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@cypher7536]

Bhaiya recursion to space optimisation khud likha pura ❤️❤️❤️

[@shreyasnagabhushan4918]

understood , amazing explanation, sets clearly in the mind

[@sachinchoudhary4142]

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

[@chanchalroy3417]

Understood! Just wow 😲

[@parthsalat]

Continue from 18:00

[@arvindjaiswal8013]

Awesome explanation...

[@chitranshjain5075]

Understood. Kudos to you for the amazing job! Can you make a playlist on Array problems too?

[@abdalla4425]

UNDERSTOOD BABY!

[@lakshaysharma6550]

UNDERSTOOD!!!🔥🔥🔥🔥🔥🔥

[@kathanvakharia]

Understood...Completed (23/56)

[@shubh625]

understood and did till space optimization on my own missed

[@sameersahu4569]

Understood Striver!!!Thank you for the amazing content

[@abhirupbasu3386]

the 1-D array part was so good. UNderstood.

[@vineetsingh4707]

Understood

[@kanchandubeyvlog]

Amazing bahot Achha padhate ho ❤️❤️

[@sahilarya9510]

aap kyuun padh rhi ho didi

[@Kunaaaal17]

UNDERSTOOD!!!! AND LOVED IT!!

[@johnsimon8158]

thanks for this awesome content

[@santoshb7776]

Understood sir !🙏🙏

[@ganeshkamath89]

Thanks Striver. Understood. Learnt a lot.

[@adityasaxena6971]

Thanks a Lot Striver🤩

[@TanviPoddar-f1k]

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.

[@SouravKumar-um7pr]

I am thinking the same

[@saumilaggarwal5233]

thnx, was able to do this by myself

[@gangsta_coder_12]

Understood 💯💯💯

[@kumarpurushottam632]

Understood Thanks You Striver 😍

[@0xrod]

Was waiting for this 😁

[@shubhamtripathidev]

buying vegetables is the variation of ninjas training on gfg

[@cinime]

Understood!! Thank you very very VERY MUCH!!!

[@iamnoob7593]

understood , Thanks striver

[@vatsalvasoya5243]

Very well explained!!

[@jeelanibasha3984]

Instead of pick to be zero cant we keep int_ min or -1e9 as we were finding the max element

[@sujitmourya8481]

understood very well

[@lakshsinghania]

hey striver, at 13:27 why didnt we write this condition statement in the base case if(wt[0]

[@Echo-942]

Look We can do it like this as well if(ind == 0){ if(weight[0]

[@Echo-942]

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.

[@dibyanikshetry3775]

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😭😭😭😭@@Echo-942

[@lakshsinghania]

@@Echo-942 aite got it! ik its 1 yr later xd but got it that time. just revising the stuffs

[@VikashYadav-px8ei]

Understood 🎉

[@sampreethmiriyala1086]

UNDERSTOOD.... Thank you striver