1
00:00:00,200 --> 00:00:01,340
Welcome back.

2
00:00:01,340 --> 00:00:08,360
Let's now discuss the pseudocode for the memoization approach that we have just now discussed for solving

3
00:00:08,360 --> 00:00:10,160
the zero one knapsack problem.

4
00:00:10,190 --> 00:00:12,470
Now we have this table over here.

5
00:00:12,470 --> 00:00:17,870
And initially we filled all the cells over here with the value minus one.

6
00:00:17,870 --> 00:00:25,610
So whenever we encounter a recursive call to the knapsack function first we will check whether depee

7
00:00:25,730 --> 00:00:30,440
at item and w is not equal to minus one.

8
00:00:30,440 --> 00:00:37,670
Because if it's not minus one, it means that we had previously computed it and stored it, and we would

9
00:00:37,670 --> 00:00:40,550
just return the value at that particular cell.

10
00:00:40,550 --> 00:00:47,420
Now, if it is equal to minus one, it would mean that we have not yet encountered this subproblem,

11
00:00:47,420 --> 00:00:50,930
and therefore we would proceed and compute the value.

12
00:00:50,930 --> 00:00:57,230
And before we return the value, we would ensure to store it at depee at item and w.

13
00:00:57,230 --> 00:01:03,650
So this is the approach that we will be taking to implement the code of the approach that we have discussed.