1
00:00:00,050 --> 00:00:05,450
Let's now write the tabulation approach for solving the zero one knapsack problem.

2
00:00:05,450 --> 00:00:05,870
Okay.

3
00:00:05,870 --> 00:00:15,560
To start with, we'll need to create a 2D dp array which has n plus one rows and w plus one columns.

4
00:00:17,090 --> 00:00:20,240
Okay, so we have discussed this in detail in the previous video.

5
00:00:20,240 --> 00:00:22,490
So let's go ahead and implement the code.

6
00:00:22,490 --> 00:00:27,140
So I can say const dp is equal to array dot from.

7
00:00:28,360 --> 00:00:31,030
And I have linked N plus one.

8
00:00:33,670 --> 00:00:34,450
Okay.

9
00:00:35,680 --> 00:00:45,790
Now over here we are going to say RA w plus one, and we will fill every cell in this 2d dp array with

10
00:00:45,790 --> 00:00:46,810
the value zero.

11
00:00:46,810 --> 00:00:47,170
Okay.

12
00:00:47,170 --> 00:00:53,260
So we have created a 2d dp array which has n plus one rows and w plus one columns.

13
00:00:53,260 --> 00:00:57,640
And we have filled every cell in this DP array with the value zero.

14
00:00:57,640 --> 00:00:59,320
Okay, now let's proceed.

15
00:00:59,320 --> 00:01:04,870
Now we have already seen that in the previous video that the first column and the first row need to

16
00:01:04,870 --> 00:01:06,370
be filled with the value zero.

17
00:01:06,370 --> 00:01:11,890
And that's taken care over here because we have in fact filled every cell in this DP array with the

18
00:01:11,890 --> 00:01:12,580
value zero.

19
00:01:12,580 --> 00:01:15,370
So now we are going to have a nested for loop.

20
00:01:15,370 --> 00:01:22,420
And I is going to take the values starting at one because we don't need to now visit the row with index

21
00:01:22,420 --> 00:01:22,930
zero.

22
00:01:22,930 --> 00:01:24,970
So that's why I starts with one.

23
00:01:24,970 --> 00:01:27,790
And I goes up to n okay.

24
00:01:28,720 --> 00:01:32,860
And then we'll have j which also starts at one.

25
00:01:33,730 --> 00:01:39,520
Because for the same reason we don't want to visit the first column or the column with index zero.

26
00:01:39,520 --> 00:01:45,370
So that's why we start with j taking the value one and j goes up to w okay.

27
00:01:45,370 --> 00:01:47,410
So j less than equal to w.

28
00:01:49,950 --> 00:01:50,580
All right.

29
00:01:50,580 --> 00:01:59,760
And now for each IJ combination we need to calculate the exclude value and the include value okay.

30
00:02:00,810 --> 00:02:03,210
So okay that's a typo.

31
00:02:03,210 --> 00:02:10,350
So let's say const exclude is equal to dp at I minus one j.

32
00:02:11,910 --> 00:02:12,270
Okay.

33
00:02:12,270 --> 00:02:13,800
So again we have discussed this.

34
00:02:13,800 --> 00:02:15,960
Now the remaining weight does not change.

35
00:02:15,960 --> 00:02:17,940
So that's why we have J itself over here.

36
00:02:17,940 --> 00:02:20,910
And then we have to exclude this particular item.

37
00:02:20,910 --> 00:02:23,310
So that's why we have I minus one over here.

38
00:02:23,460 --> 00:02:24,840
That's exclude okay.

39
00:02:24,840 --> 00:02:27,300
Now let's go ahead and calculate include.

40
00:02:27,300 --> 00:02:34,320
Now initially we will set include to equal zero because we cannot always include the item.

41
00:02:34,320 --> 00:02:42,870
And ultimately over here we would have to say DP at IJ is the maximum between exclude and include okay.

42
00:02:47,310 --> 00:02:51,750
So that is why we need a value over here for the include variable.

43
00:02:51,750 --> 00:02:54,330
And that's why initially we are setting it to zero.

44
00:02:54,330 --> 00:03:00,840
And then we proceed and check whether the weight of this particular item is less than or equal to the

45
00:03:00,840 --> 00:03:02,430
remaining weight, which is J.

46
00:03:02,430 --> 00:03:02,760
Okay.

47
00:03:02,760 --> 00:03:09,090
So if weight at I minus one less than equal to j.

48
00:03:09,090 --> 00:03:11,490
And again over here we have to do I minus one.

49
00:03:11,490 --> 00:03:13,410
And we have discussed the reason for this.

50
00:03:13,410 --> 00:03:16,770
That is because the weight and value array are zero indexed.

51
00:03:16,800 --> 00:03:19,680
Now again we have discussed this in detail in the previous video.

52
00:03:19,680 --> 00:03:22,020
So I'm just proceeding with the solution over here.

53
00:03:22,020 --> 00:03:28,380
So if weight at I minus one is less than or equal to j then we can include it.

54
00:03:28,380 --> 00:03:39,690
So in that case include would be equal to value at I minus one plus d p at I minus one j minus weight

55
00:03:39,690 --> 00:03:43,230
at I minus one okay.

56
00:03:43,230 --> 00:03:49,680
So over here j minus weight at I minus one gives us the remaining weight after deducting the weight

57
00:03:49,680 --> 00:03:52,260
of the item that has been added to the knapsack.

58
00:03:52,260 --> 00:03:56,760
And then over here we have at I minus one because we have used the ith element.

59
00:03:56,760 --> 00:03:59,040
So we have to go to the previous element.

60
00:03:59,040 --> 00:04:01,230
And that's what we have done over here as well okay.

61
00:04:01,230 --> 00:04:03,330
So this will give us the include value.

62
00:04:03,330 --> 00:04:09,810
And then over here we are assigning depee at I j with the value which is the greater value between exclude

63
00:04:09,810 --> 00:04:10,920
and include.

64
00:04:10,920 --> 00:04:11,640
And.

65
00:04:11,640 --> 00:04:14,160
In this way we will fill the DP table.

66
00:04:14,160 --> 00:04:19,290
And then finally we can just return depee at n w.

67
00:04:20,160 --> 00:04:22,020
And that will give us the answer.

68
00:04:22,350 --> 00:04:26,700
Okay, now let's go ahead and run this code and see if it's passing all the test cases.

69
00:04:29,070 --> 00:04:30,570
All right, so it's working.

70
00:04:30,570 --> 00:04:32,070
It's passing all the test cases.

71
00:04:32,070 --> 00:04:36,990
And again remember DPI at n w is the last element of the table.

72
00:04:36,990 --> 00:04:39,270
And that would be representing the answer.

73
00:04:39,270 --> 00:04:42,150
And we have discussed this in detail in the previous video.