01 Knapsack using Memoization | Concept of Memoization

In this video, I have explained the basic concepts of memoization using 01 knapsack as an example.I have already explained the 01 knapsack using recursion method in my previous video and here I have continued the topic and showed how to apply smart recursion using an additional data structure.Remembering previously calculated subproblem values so as to not recalculate will improve time complexity and that's the goal of using memoization.We can remember the past by storing results in certain data structures which is generally array or map.I have first shown the example for why we need optimization on recursion and then I have shown how to optimize the recursion by using simple examples and code explanation.
If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
========================================================================
USEFUL LINKS:
01 Knapsack Recursion: • 01 Knapsack using Recu...
01 Knapsack DP: • 01 Knapsack Tabulation...
#01knapsack #dp #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 😀

[@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

[@development3090]

His voice is so satisfying.

[@techdose4u]

😂

[@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

[@tusharbarman1924]

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

[@aayush5474]

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

[@techdose4u]

😀

[@sakshamsharma5484]

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

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

[@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]

👍

[@padmaraghunathan4849]

Sir, thanks for the crystal clear explanation!!!

[@kunalsoni7681]

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

[@techdose4u]

Thanks :)

[@impatientgaming9868]

good one.

[@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

[@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?

[@panmacabre9895]

your channel is the best

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

[@abdelhakimlamnaouar9527]

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

[@ivanturko8881]

Priceless!

[@tahirm09]

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

[@techdose4u]

Welcome :)

[@isacitrabuana8689]

thank you

[@maddinenianilkumar8737]

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

[@dhanashreegodase4445]

excellent!!!!! Thank you so much

[@techdose4u]

Welcome :)

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

[@mpavankumar6695]

Thanks

[@ajayaman46]

Superb

[@techdose4u]

Thanks :)

[@techmoon_]

thanks a lot bro u rock

[@techdose4u]

Welcome

[@syedkaja2045]

superb😀

[@techdose4u]

Thanks

[@DEVANSHGOEL-dq1wh]

thank you sir

[@techdose4u]

Welcome

[@Sandeep-lm5yi]

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

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@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 👍🏼