1
00:00:00,080 --> 00:00:04,340
Let's now write these space optimized tabulation approach.

2
00:00:04,340 --> 00:00:07,610
So this is the tabulation approach that we had previously written.

3
00:00:07,610 --> 00:00:09,920
And we had used a 2D array.

4
00:00:09,920 --> 00:00:15,230
But as we have discussed in the previous video, we will not be needing this when we go ahead with the

5
00:00:15,230 --> 00:00:20,960
space optimized tabulation approach, we will need two arrays which are of size w plus one.

6
00:00:20,960 --> 00:00:23,240
So let's call them prev and curr okay.

7
00:00:23,240 --> 00:00:25,730
So let prev equal to array.

8
00:00:26,300 --> 00:00:30,260
And the size is going to be w plus one okay.

9
00:00:30,260 --> 00:00:34,610
And we will fill every cell in this array initially with the value zero.

10
00:00:34,610 --> 00:00:38,600
And we will do the same thing with one more array which we can just call curr.

11
00:00:38,600 --> 00:00:41,720
And this also is going to be of size w plus one.

12
00:00:41,720 --> 00:00:45,530
And we will fill every cell in this array with the value zero.

13
00:00:45,980 --> 00:00:46,460
Alright.

14
00:00:46,490 --> 00:00:53,390
Now we proceed over here I takes the value from one up to n and j takes the value from one up to w.

15
00:00:53,390 --> 00:00:54,830
So there is no change over here.

16
00:00:54,830 --> 00:01:01,400
And for exclude wherever we have DPI at I minus one, we replace this with prev.

17
00:01:01,400 --> 00:01:01,760
Okay.

18
00:01:01,760 --> 00:01:06,290
So this is going to be prev at j and initially include is set to zero.

19
00:01:06,290 --> 00:01:13,610
And if weight at I minus one less than equal to j then include is equal to value at I minus one plus

20
00:01:13,610 --> 00:01:15,770
instead of dpi at I minus one.

21
00:01:15,770 --> 00:01:17,810
We will replace this with prev.

22
00:01:17,810 --> 00:01:22,220
So this would be prev at j minus weight at I minus one okay.

23
00:01:22,220 --> 00:01:25,040
And over here we have dpi at I j.

24
00:01:25,040 --> 00:01:27,740
And again we don't have a 2D dpi array over here.

25
00:01:27,740 --> 00:01:31,010
So instead of this we will set this to curve.

26
00:01:31,010 --> 00:01:32,720
So over here we have DPI at I.

27
00:01:32,720 --> 00:01:34,340
And that would be changed to CR.

28
00:01:34,340 --> 00:01:38,330
So whenever we had DPI at I minus one we changed it to prev.

29
00:01:38,330 --> 00:01:41,090
And when we have DPI at I we change it to CR.

30
00:01:41,090 --> 00:01:47,270
So this over here becomes CR at j is equal to math dot max between exclude and include.

31
00:01:47,270 --> 00:01:48,440
And that's it.

32
00:01:48,440 --> 00:01:53,780
Now there's one more thing that we have to do, which is that after going through all the values for

33
00:01:53,780 --> 00:02:00,140
j for a particular value of I that is over here, we will have to set prev two.

34
00:02:00,140 --> 00:02:02,330
What is there in CR at this point?

35
00:02:02,330 --> 00:02:02,600
Okay.

36
00:02:02,600 --> 00:02:06,830
So we can say prev is equal to CR dot slice okay.

37
00:02:06,830 --> 00:02:08,690
So this makes a deep copy.

38
00:02:08,690 --> 00:02:10,700
And then we proceed okay.

39
00:02:10,700 --> 00:02:14,420
And finally over here we are returning DPI at n w.

40
00:02:14,420 --> 00:02:17,780
And instead of DPI at n we'd have to replace this with CR.

41
00:02:18,170 --> 00:02:19,010
And that's it.

42
00:02:19,010 --> 00:02:24,560
So this is the space optimized tabulation approach for solving the zero one knapsack problem.

43
00:02:24,560 --> 00:02:29,180
Now let's go ahead and run this code and see if it's passing all the test cases.

44
00:02:29,870 --> 00:02:31,640
And you can see that it's working.

45
00:02:31,640 --> 00:02:33,620
It's passing all the test cases.