01 Knapsack using Memoization | Concept of Memoization

[@bestsaurabh]

What you explained is the top-down approach having recursive calls. For iterative solution where we solve the smaller problem first and build on top of that is called bottom up approach.

[@techdose4u]

Yes you are right. In terms of subproblems Memoization is Top-down and Tabulation is bottom up. But I am used to talking in terms of directions in a table. If you fill top-down and left-right then it's actually bottom-up but due to direction, I am used to saying Top-Down.

[@schan263]

@@techdose4u Thanks for clearing that up. I was a bit confused when you said top down at the end of the video.

[@nagendrahegde]

Hey, this video actually made me understand knapsack solution! I am preparing for this big ass interview where mostly they will ask DP problems. I was struggling with the knapsack problem and could not understand well from gfg (btw, the content in gfg is great, but it was something with me that i could not somehow feeling the intuition). But after watching this video, i could easily corelate. Thanks dude!

[@techdose4u]

Welcome 😀

[@tusharbarman1924]

Better than all the other videos out there, thanks a lot man.

[@development3090]

His voice is so satisfying.

[@techdose4u]

😂

[@padmaraghunathan4849]

Sir, thanks for the crystal clear explanation!!!

[@panmacabre9895]

your channel is the best

[@akashchaudhary8066]

Sir, it's a great feeling to learn from you, one kind request though, please attach some practice problems related to the topics you teach in every video, I wanted to learn dp from a long time

[@techdose4u]

I will do problems after concepts. You can practice those.

[@akashchaudhary8066]

@@techdose4u Yeah you said that in your live stream, but if you can attach hand picked problem links, it'll be great help, either way you're great , keep up the good work

[@kunalsoni7681]

Very nice and helpful video to understanding deeply of knapsack problem 🥰😊😍

[@techdose4u]

Thanks :)

[@tahirm09]

Dear Sir, Thanks you vary much, Appreciate!!! you approach

[@techdose4u]

Welcome :)

[@aayush5474]

Itni raat ko upload sone hi jaa rha tha par video dekhunga😂

[@techdose4u]

😀

[@vivek.tiwary]

In 2 d array, column should go till 10 that is the max capacity. Sometimes you are saying capacity 5, and you are calculating for 10, hell lot of confusion

[@sridharanshooriya772]

16:18, result would be set to memo array when all the recursion calls been done right? I mean the program would go to the block when the computation is been over, I'm pretty confused on how memorization works. Great video, understood like a charm. Thank you ❤️❤️

[@techdose4u]

Yes right. Welcome :)

[@dhanviakash726]

Yeah Actually it's not using the mem table that we created to lookup I put a counter on that lookup block if(mem[n-1][capacity-1] != -1){ counter++; return mem[n-1][capacity-1]; } My counter value is 0 after program has finished

[@codingexception6502]

bhai result store karne ke liye mem[N][W] hoga na? ki mem[W][N] I am confused kyuki video main mem[W][N] hai but diagram(pichle slide) mein alag hai. Also ye array ka logic samaz nahi aa rha hai

[@techdose4u]

Yes you are right. I must have written by mistake.Thanks for letting everyone know.

[@codingexception6502]

@@techdose4u Thanks for such a prompt reply. Ek doubt solve hogaya. another doubt is ki fibonacci example main hum ek hi array lete hai but isme 2-D array of no. of elements as row and weight as column. I am not getting it. kyuki maine jab dry run kia normal recursion wale code ka usme mujhe koi weight + num of element repeat hote hue nahi mila. I am confused because of that.

[@vijayj1997]

Great Explanation , can you explain manacher's algorithm its very confusing

[@gajanoor]

Thanks a lot for the video. Appreciate your help. Shouldn't the base check be N < 0 instead of N == 0? Assuming the N value passed into the function is zero-indexed?

[@abdelhakimlamnaouar9527]

how can we know if our memoization solution will be getting stack overflow or not?

[@sridharanshooriya772]

*Those who are working on with Java, here's the code. Ty so much surya for helping me do it. capacity) { result =(getOptimalValue(capacity,values,weights,n-1,mem)); }else { result = Math.max(getOptimalValue(capacity,values,weights,n-1,mem), getOptimalValue(capacity-weights[n-1],values,weights,n-1,mem)+values[n-1]); mem[n-1][capacity-1]= result; } } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int capacity = sc.nextInt(); int[] values = new int[n]; int[] weights = new int[n]; for (int i = 0; i < n; i++) { values[i] = sc.nextInt(); weights[i] = sc.nextInt(); } int mem[][] = new int[n][capacity]; for(int i = 0;i

[@techdose4u]

👍

[@dhanashreegodase4445]

excellent!!!!! Thank you so much

[@techdose4u]

Welcome :)

[@ivanturko8881]

Priceless!

[@impatientgaming9868]

good one.

[@syedkaja2045]

superb😀

[@techdose4u]

Thanks

[@KonNishant]

Great video, but if you will explain recursion part little bit more precise then it will be very helpful to those who gets stuck with recursion.

[@techdose4u]

Recursion is in the previous video. Please comment there if you get any issues related to recursion.

[@techmoon_]

thanks a lot bro u rock

[@techdose4u]

Welcome

[@ajayaman46]

Superb

[@techdose4u]

Thanks :)

[@maddinenianilkumar8737]

Sir, how to store 0/1 in a solution array to indicate which item is included and which is not?

[@abhishekjaiswal2575]

I have a doubt that can we travel from 0 to n and increase n+1 every time. I mean can we move from left to right in weight array.

[@sakshamsharma5484]

I think base case should be N < 0 instead of N == 0 since we have an zero indexed array .

[@mwshubham]

16:15 mem[w][n] or mem[n][w] ?

[@mwshubham]

Btw amazing video learning this topic today.

[@techdose4u]

I think I wrote something wrong. Please check it 😅

[@mwshubham]

@@techdose4u yup no worries. Thanks for your reply.

[@techdose4u]

@@mwshubham 👍🏼

[@DEVANSHGOEL-dq1wh]

thank you sir

[@techdose4u]

Welcome

[@isacitrabuana8689]

thank you

[@mpavankumar6695]

Thanks

[@Sandeep-lm5yi]

For all those looking for practice problems Here you go: atcoder.jp/contests/dp/tasks

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍