1
00:00:00,200 --> 00:00:07,160
We have discussed the recursive approach and the memoization approach, and for the memoization approach,

2
00:00:07,160 --> 00:00:12,440
the time and space complexity were of the order of n into W.

3
00:00:12,470 --> 00:00:19,070
Now let's get started with the bottom up or tabulation approach for solving the zero one knapsack problem.

4
00:00:19,670 --> 00:00:26,870
Now again for this, let's take the same example where we are given three items and the maximum capacity

5
00:00:26,870 --> 00:00:29,510
of the knapsack is eight units.

6
00:00:29,540 --> 00:00:33,950
Now over here we will again need a DP table.

7
00:00:33,980 --> 00:00:36,110
Now let's draw that over here.

8
00:00:36,110 --> 00:00:42,140
So I have in this case four rows even though I just have three items.

9
00:00:42,140 --> 00:00:46,280
And again I have columns over here which go from zero up to eight.

10
00:00:46,310 --> 00:00:49,280
Now this is similar to the memoization table.

11
00:00:49,280 --> 00:00:55,820
Now you could have an extra row as you have over here in the case of memoization as well.

12
00:00:55,820 --> 00:00:58,100
But then that's not needed over there.

13
00:00:58,100 --> 00:01:00,410
And that's why I've not included it there.

14
00:01:00,410 --> 00:01:06,500
But in the tabulation approach, it's very helpful to have this row over here, because as you will

15
00:01:06,500 --> 00:01:11,840
see, we will be using values from a previous row to fill values in the next row.

16
00:01:11,840 --> 00:01:20,210
So this row over here, which indicates not having any item, is useful for setting the initial conditions,

17
00:01:20,210 --> 00:01:23,330
which can be used for filling the next row over here.

18
00:01:23,330 --> 00:01:25,400
So let's just have this over here.

19
00:01:25,400 --> 00:01:30,380
And once we do a dry run the utility of this will become very clear.

20
00:01:30,380 --> 00:01:31,640
So let's get started.

21
00:01:31,670 --> 00:01:38,120
Now we had previously discussed that in the tabulation or bottom up approach, the initial conditions

22
00:01:38,120 --> 00:01:43,070
will be similar to the base case that you have in the recursive approach.

23
00:01:43,070 --> 00:01:49,400
The base case in the recursive approach was indicative of let's say the remaining weight is zero.

24
00:01:49,400 --> 00:01:55,250
In that case we would return zero, or if there is no valid item, we would return zero.

25
00:01:55,250 --> 00:01:59,660
So again this is the initial condition for the tabulation approach.

26
00:01:59,660 --> 00:02:05,030
So if W is zero which indicates this column then the value is going to be zero.

27
00:02:05,030 --> 00:02:11,990
Or if n is equal to zero, or if there are no items which is indicated by this row, the values are

28
00:02:11,990 --> 00:02:12,920
going to be zero.

29
00:02:12,920 --> 00:02:19,010
So we're going to fill this row over here and this column over here with the value zero.

30
00:02:19,010 --> 00:02:20,060
So let's do that.

31
00:02:22,980 --> 00:02:23,790
All right.

32
00:02:23,790 --> 00:02:32,280
Notice over here that there is no need to initialize values, as we had done in the case of memoization.

33
00:02:32,280 --> 00:02:37,590
In the case of memoization, we had filled each of these cells with the value minus one.

34
00:02:37,590 --> 00:02:44,130
And we use that to understand whether we had already computed a value or whether we had to go ahead

35
00:02:44,130 --> 00:02:45,210
and compute it.

36
00:02:45,210 --> 00:02:51,780
But over here we don't need that because we will be going row by row, which means that first we will

37
00:02:51,780 --> 00:02:52,740
fill this cell.

38
00:02:52,740 --> 00:02:55,080
Then we will proceed and fill this cell.

39
00:02:55,080 --> 00:03:01,920
And in this manner we will go through each cell over here till finally we come over here.

40
00:03:01,920 --> 00:03:04,650
And this is where we will get the answer.

41
00:03:04,650 --> 00:03:09,600
Now let's discuss how to find the value of a particular cell.

42
00:03:09,600 --> 00:03:11,970
Now let's call this table depee.

43
00:03:12,840 --> 00:03:21,420
And if the rows over here are indicated by I, and if the columns over here are indicated by J, then

44
00:03:21,420 --> 00:03:25,950
we can denote the value of a cell as depee at I and j.

45
00:03:26,550 --> 00:03:29,340
Now how do we calculate this value?

46
00:03:29,370 --> 00:03:34,830
Now it's going to have the same logic as for the recursive approach.

47
00:03:34,830 --> 00:03:42,840
So we have an option to exclude the item at hand which would be depee at I minus one j.

48
00:03:42,990 --> 00:03:44,790
And again j is the weight.

49
00:03:44,790 --> 00:03:51,030
So when you exclude an item, notice that the remaining weight that can be added to the knapsack remains

50
00:03:51,030 --> 00:03:51,690
the same.

51
00:03:51,690 --> 00:03:53,430
So over here also you have J.

52
00:03:53,430 --> 00:03:55,500
And over here also you have J.

53
00:03:55,500 --> 00:04:02,070
But then you have one item less which is what you are doing over here when you're saying I minus one.

54
00:04:02,070 --> 00:04:07,860
So that's the exclude case where the same weight can still be added to the knapsack.

55
00:04:07,860 --> 00:04:13,680
But you have one item less so exclude is equal to dp at I minus one j.

56
00:04:13,680 --> 00:04:17,880
And then you have to compute the include case for include.

57
00:04:17,880 --> 00:04:25,020
Also you would have one item less, but the value has to be changed because you have included an item,

58
00:04:25,020 --> 00:04:29,910
and the remaining weight that can be added to the knapsack has to be reduced.

59
00:04:29,910 --> 00:04:39,570
So include is going to equal value at I minus one plus dp at I minus one, and j minus weight at I minus

60
00:04:39,570 --> 00:04:40,020
one.

61
00:04:40,020 --> 00:04:48,330
Now over here notice that we have said value at I minus one, even though we included the value that

62
00:04:48,330 --> 00:04:49,230
we were considering.

63
00:04:49,230 --> 00:04:50,040
Now why is that?

64
00:04:50,040 --> 00:04:52,560
So let's try to understand that now.

65
00:04:52,560 --> 00:04:55,590
For example, let's say we are filling this cell over here.

66
00:04:55,590 --> 00:05:01,560
So when we are trying to fill this cell and when we are calculating the include value, and when we

67
00:05:01,560 --> 00:05:09,270
say that value at I minus one, what we want to achieve is we want to add the value of the first item.

68
00:05:09,270 --> 00:05:17,340
Now notice that the value array and the weight array are zero indexed, and the index of the first item

69
00:05:17,340 --> 00:05:18,540
is going to be zero.

70
00:05:18,540 --> 00:05:24,240
But over here we are talking about item one, because we have already filled the value over here as

71
00:05:24,240 --> 00:05:31,470
zero for the case where we are not taking any item, and then we have the cases of item one, item one

72
00:05:31,470 --> 00:05:33,780
and two, and item three up to one.

73
00:05:33,780 --> 00:05:34,140
Right.

74
00:05:34,140 --> 00:05:38,430
So over here I is going to take the value one in the DP array.

75
00:05:38,430 --> 00:05:41,040
But it's indicative of the first item.

76
00:05:41,040 --> 00:05:44,160
And because the value and weight array are zero indexed.

77
00:05:44,160 --> 00:05:48,090
That's why over here we have to do I minus one.

78
00:05:48,090 --> 00:05:55,110
And again it's the same logic for weight of I minus one over here as well, because we want to subtract

79
00:05:55,110 --> 00:06:01,980
the weight of the included item from the remaining weight that can be added to the knapsack.

80
00:06:01,980 --> 00:06:08,160
So we have understood why we have value at I minus one over here and weight at I minus one over here.

81
00:06:08,160 --> 00:06:17,010
But over here we have DP at I minus one because we have added the item and we just have one item less.

82
00:06:17,400 --> 00:06:24,060
So the reason for I minus one over here and here is different for the I minus one over here.

83
00:06:24,060 --> 00:06:27,840
Now again notice over here also we had DP at I minus one j.

84
00:06:27,840 --> 00:06:35,610
That was because we wanted one item less and we wanted to go one row above in the DP table, which is

85
00:06:35,610 --> 00:06:36,600
what we have over here.

86
00:06:36,600 --> 00:06:44,850
So whenever you are dealing with an item in the ith row in the DP array, to convert an identify that

87
00:06:44,850 --> 00:06:50,790
item's value and weight, you have to do I minus one, which is what we have done over here and over

88
00:06:50,790 --> 00:06:51,150
here.

89
00:06:51,150 --> 00:06:51,750
All right.

90
00:06:51,750 --> 00:06:54,090
So we have found the remaining weight over here.

91
00:06:54,090 --> 00:07:01,080
And we are going one row up because we want to think of the remaining items that we have.

92
00:07:01,080 --> 00:07:01,830
All right.

93
00:07:01,830 --> 00:07:06,660
So we have seen what exclude is and we have seen what include is.

94
00:07:06,660 --> 00:07:12,330
Now let's just walk through and see how the algorithm would fill this table.

95
00:07:12,330 --> 00:07:19,500
So the first cell that we are trying to fill is this one over here where we have just item one.

96
00:07:19,500 --> 00:07:23,160
And the remaining weight that can be added is one.

97
00:07:23,160 --> 00:07:26,760
Now there are two possibilities exclude and include.

98
00:07:26,760 --> 00:07:34,470
Now exclude is having no item because we are excluding this item and we just had one item to start with.

99
00:07:34,470 --> 00:07:38,460
So when we exclude this we have no item.

100
00:07:38,460 --> 00:07:40,560
So that's dp I minus one.

101
00:07:40,560 --> 00:07:47,160
So we are coming to this row where we don't have any item and the remaining weight stays the same which

102
00:07:47,160 --> 00:07:48,090
is one itself.

103
00:07:48,090 --> 00:07:53,490
So notice that this zero gives us the value of dp I minus one j.

104
00:07:53,580 --> 00:07:55,680
So that's the exclude value.

105
00:07:55,680 --> 00:08:02,880
And then when we are trying the include case notice over here the weight of the first item is eight

106
00:08:02,880 --> 00:08:09,090
and the remaining weight that we have at this point that can be added to the knapsack is just one.

107
00:08:09,090 --> 00:08:11,940
So we are not able to include this item.

108
00:08:11,940 --> 00:08:12,450
So in.

109
00:08:12,610 --> 00:08:17,380
Load is also set to zero, so exclude is zero and include is zero.

110
00:08:17,380 --> 00:08:20,530
So the maximum between these two is zero itself.

111
00:08:20,530 --> 00:08:23,530
And thus we can fill over here zero.

112
00:08:24,610 --> 00:08:25,900
Now in a similar manner.

113
00:08:25,900 --> 00:08:32,140
You will see that over here also, because the weight of the first item is eight, we will not be able

114
00:08:32,140 --> 00:08:39,550
to include it in any of these cases, because the weight of this item is not less than or equal to any

115
00:08:39,550 --> 00:08:40,510
of these weights.

116
00:08:40,510 --> 00:08:48,940
So for all these cases include is going to be equal to zero and exclude as we have seen is just depee

117
00:08:48,940 --> 00:08:53,950
I minus one j, which is the value that we have in the previous row.

118
00:08:53,950 --> 00:08:57,400
So for this cell the exclude value is this.

119
00:08:57,400 --> 00:08:59,800
For this cell the exclude value is this.

120
00:08:59,800 --> 00:09:02,200
For this cell the exclude value is this.

121
00:09:02,200 --> 00:09:04,030
And it goes on in this manner.

122
00:09:04,030 --> 00:09:06,520
So include is zero for all of these.

123
00:09:06,520 --> 00:09:09,250
And exclude is also zero for all of these.

124
00:09:09,250 --> 00:09:13,060
Therefore we can just fill zero in all these places.

125
00:09:13,150 --> 00:09:16,240
Now when we come to this cell over here.

126
00:09:17,270 --> 00:09:20,570
Notice that again, exclude is still zero.

127
00:09:20,570 --> 00:09:22,370
That's the value that we have over here.

128
00:09:22,370 --> 00:09:31,430
And we are able to include the item at hand because the weight of the item one is eight, and the remaining

129
00:09:31,430 --> 00:09:34,130
weight that can be added over here is also eight.

130
00:09:34,130 --> 00:09:40,580
So the value of include over here becomes value at I minus one I is equal to one.

131
00:09:40,580 --> 00:09:42,500
So over here I is equal to one.

132
00:09:42,680 --> 00:09:47,990
So value at I minus one is value at one minus one, which is value at zero.

133
00:09:47,990 --> 00:09:49,520
And this is index zero right.

134
00:09:49,520 --> 00:09:50,810
So value at zero is two.

135
00:09:50,840 --> 00:09:52,130
So this becomes two.

136
00:09:52,130 --> 00:09:56,750
And then we have dp at I minus one which is this row over here.

137
00:09:56,750 --> 00:09:59,750
And j minus weighted I minus one.

138
00:09:59,750 --> 00:10:04,460
Now weight at I minus one has to be subtracted from j.

139
00:10:04,460 --> 00:10:06,020
So j over here is eight.

140
00:10:06,020 --> 00:10:07,370
So let's write that over here.

141
00:10:07,370 --> 00:10:12,080
And weight at I minus one is weight at zero which is this eight itself.

142
00:10:12,080 --> 00:10:14,510
So we get eight minus eight over here.

143
00:10:14,510 --> 00:10:18,320
And over here I minus one is one minus one which is zero.

144
00:10:18,320 --> 00:10:25,670
So this term over here becomes DP at zero zero which is zero itself.

145
00:10:25,670 --> 00:10:32,000
So include becomes two plus DP at zero zero which is two plus zero okay.

146
00:10:32,000 --> 00:10:34,370
So we have exclude as zero.

147
00:10:34,370 --> 00:10:35,480
This is exclude.

148
00:10:36,190 --> 00:10:41,590
And include is two plus zero, which is two, and the maximum between 0 and 2 is two.

149
00:10:41,620 --> 00:10:43,870
So we fill two over here.

150
00:10:45,310 --> 00:10:46,780
And we're done with this row.

151
00:10:46,810 --> 00:10:51,280
Now let's proceed to the next row, and let's fill this cell over here.

152
00:10:51,310 --> 00:10:56,170
Again notice the exclude value is just going to be this value over here.

153
00:10:56,650 --> 00:10:57,130
All right.

154
00:10:57,130 --> 00:11:01,240
So for this cell exclude is going to be this value over here.

155
00:11:01,240 --> 00:11:04,540
And can we include this value.

156
00:11:04,540 --> 00:11:05,770
So let's take a look at that.

157
00:11:05,770 --> 00:11:09,100
So the weight that can be added at this point is one.

158
00:11:09,100 --> 00:11:12,040
And the weight of item two is two.

159
00:11:12,070 --> 00:11:13,390
So we cannot add it.

160
00:11:13,390 --> 00:11:15,700
And therefore include is also zero.

161
00:11:15,700 --> 00:11:19,750
And therefore the maximum between 0 and 0 is just zero.

162
00:11:19,900 --> 00:11:22,570
Now what about the next cell over here.

163
00:11:22,570 --> 00:11:25,360
Again exclude is going to be zero.

164
00:11:25,360 --> 00:11:27,430
But what about include.

165
00:11:27,430 --> 00:11:33,430
Now the weight of item two is two and the remaining weight that can be added is also equal to two.

166
00:11:33,460 --> 00:11:35,950
So we can include this item.

167
00:11:35,950 --> 00:11:39,670
And if we do include it we are going to get this value.

168
00:11:39,670 --> 00:11:40,870
Because over here.

169
00:11:41,590 --> 00:11:43,360
I is going to be equal to two.

170
00:11:43,360 --> 00:11:47,980
So value at two minus one is value at one, which is this value which is three.

171
00:11:47,980 --> 00:11:50,020
So we get value of three over here.

172
00:11:50,020 --> 00:11:53,860
And dp at I minus one is the previous row okay.

173
00:11:53,860 --> 00:11:55,510
So two minus one is one.

174
00:11:55,510 --> 00:11:57,130
So this is going to be equal to one.

175
00:11:57,130 --> 00:12:05,500
And then we have j which is two minus wait at this index over here which is one because over here I

176
00:12:05,500 --> 00:12:06,130
is two right.

177
00:12:06,130 --> 00:12:09,490
So wait at two minus one is wait at one which is two.

178
00:12:09,520 --> 00:12:11,680
So we have two minus two over here.

179
00:12:11,680 --> 00:12:18,430
So include is going to be three plus depee at one and then two minus two which is zero.

180
00:12:18,430 --> 00:12:19,750
So DP at one.

181
00:12:19,750 --> 00:12:23,800
That's this row over here at index zero is zero itself.

182
00:12:23,800 --> 00:12:26,770
So this is three plus zero which is three.

183
00:12:26,770 --> 00:12:29,530
So maximum between 0 and 3 is three.

184
00:12:29,530 --> 00:12:31,390
So we can fill over here three.

185
00:12:32,700 --> 00:12:35,130
Now let's proceed to the next cell.

186
00:12:35,130 --> 00:12:35,790
Again.

187
00:12:35,790 --> 00:12:43,050
Exclude is going to be equal to zero and include at this point is going to be three plus because the

188
00:12:43,050 --> 00:12:45,870
value of item two is three we have seen that.

189
00:12:45,870 --> 00:12:50,010
So it's going to be three plus depee at one which is the previous row.

190
00:12:50,010 --> 00:12:55,920
And then you have three which is this three over here minus the weight of the item that's included which

191
00:12:55,920 --> 00:12:56,430
is two.

192
00:12:56,460 --> 00:12:59,280
So you get DP at one comma one okay.

193
00:12:59,280 --> 00:13:02,790
So that's this value over here which is zero itself.

194
00:13:02,790 --> 00:13:05,130
And the maximum between 0 and 3 is three.

195
00:13:05,130 --> 00:13:06,660
So we fill three over here.

196
00:13:06,660 --> 00:13:08,760
Let's proceed to the next cell.

197
00:13:09,180 --> 00:13:13,020
And again over here you can see that exclude is again zero.

198
00:13:13,020 --> 00:13:16,980
But when it comes to include you have three plus depee at one.

199
00:13:16,980 --> 00:13:23,010
And then you have this four minus two and DP at one and four minus two which is two.

200
00:13:23,040 --> 00:13:24,420
Is this zero itself.

201
00:13:24,420 --> 00:13:26,790
So over here of zero and you have three.

202
00:13:26,790 --> 00:13:28,860
And the maximum between these two is three.

203
00:13:28,860 --> 00:13:32,490
So we fill three over here we proceed to the next cell.

204
00:13:32,490 --> 00:13:39,570
Again exclude is zero and include is going to be three plus depee at one and then five minus two.

205
00:13:39,570 --> 00:13:43,440
And over here that's three and DP at one and three.

206
00:13:43,470 --> 00:13:46,380
Is this cell over here which is again zero.

207
00:13:46,380 --> 00:13:49,710
So between 0 and 3 the maximum is three.

208
00:13:49,710 --> 00:13:53,700
So we fill three over here we proceed to the next cell.

209
00:13:53,700 --> 00:13:57,450
And over here again exclude is zero.

210
00:13:57,450 --> 00:13:59,640
And you will see that include is three.

211
00:14:00,150 --> 00:14:02,070
And therefore we can fill three.

212
00:14:02,070 --> 00:14:04,650
Over here we proceed to the next cell.

213
00:14:04,650 --> 00:14:09,000
Over here again exclude is zero and include is going to be three.

214
00:14:09,000 --> 00:14:10,620
So we can fill that over here.

215
00:14:10,620 --> 00:14:12,330
So we get three again over here.

216
00:14:13,210 --> 00:14:17,020
And finally we come to this cell over here again.

217
00:14:17,020 --> 00:14:25,660
Exclude at this point is going to be equal to two and include is going to be three plus depee at one

218
00:14:25,660 --> 00:14:27,280
and eight minus two.

219
00:14:27,280 --> 00:14:31,720
Because this is eight and from eight you have to subtract two.

220
00:14:31,750 --> 00:14:33,910
So dp at one six.

221
00:14:34,680 --> 00:14:35,700
Is again zero.

222
00:14:35,700 --> 00:14:37,200
So over here you have two.

223
00:14:37,200 --> 00:14:38,400
And over here you have three.

224
00:14:38,400 --> 00:14:40,530
And the maximum between these two is three.

225
00:14:40,530 --> 00:14:42,720
So that's why you can fill three over here as well.

226
00:14:42,720 --> 00:14:44,700
And we're done with the second row.

227
00:14:44,700 --> 00:14:50,790
Now let's proceed to the next row again for this cell exclude is going to be equal to zero.

228
00:14:50,790 --> 00:14:53,490
And include is also going to be equal to zero.

229
00:14:53,490 --> 00:14:58,140
Because we will not be able to include item three because its weight is five.

230
00:14:58,140 --> 00:15:01,170
And the remaining weight that can be added is only one.

231
00:15:01,170 --> 00:15:08,190
So for all these values one up to four, we will not be able to include that item and we can just fill

232
00:15:08,190 --> 00:15:11,400
the value from exclude, which is what we have over here.

233
00:15:11,400 --> 00:15:15,150
So we can say zero, three, three and three over here.

234
00:15:15,150 --> 00:15:22,170
Now when we come over here, exclude is going to be the value three and include is going to be equal

235
00:15:22,170 --> 00:15:27,120
to this nine over here plus depee at two.

236
00:15:28,680 --> 00:15:36,990
And then wait is five this five minus wait at two, which is the weight of this item which is five.

237
00:15:36,990 --> 00:15:38,790
So that's five minus five.

238
00:15:38,790 --> 00:15:41,430
So DP at two and then zero.

239
00:15:41,430 --> 00:15:44,100
That's this value over here which is zero itself.

240
00:15:44,100 --> 00:15:47,760
So you have exclude to be three and include is nine.

241
00:15:47,760 --> 00:15:50,460
And the maximum between 3 and 9 is nine.

242
00:15:50,460 --> 00:15:52,560
So we will fill nine over here.

243
00:15:52,560 --> 00:15:54,540
Now let's proceed to the next cell.

244
00:15:54,540 --> 00:15:57,600
Now over here again exclude is going to be equal to three.

245
00:15:57,600 --> 00:16:02,610
And include is going to be equal to nine plus DP at two.

246
00:16:02,610 --> 00:16:06,570
And then you have six minus five six minus five is one.

247
00:16:06,570 --> 00:16:09,270
So DP at two and one is again zero.

248
00:16:09,270 --> 00:16:12,210
So this term over here becomes zero.

249
00:16:12,210 --> 00:16:14,370
And then you have three and nine over here.

250
00:16:14,370 --> 00:16:16,770
And the maximum between these two is nine.

251
00:16:16,770 --> 00:16:18,150
So we feel nine over here.

252
00:16:18,150 --> 00:16:20,220
We proceed to the next cell.

253
00:16:20,220 --> 00:16:22,590
Again exclude is going to be equal to three.

254
00:16:22,590 --> 00:16:26,490
And include is going to be equal to nine plus depee at two.

255
00:16:26,490 --> 00:16:30,210
And then you have seven minus five over here because you have seven over here.

256
00:16:30,210 --> 00:16:31,380
So that's this seven.

257
00:16:31,380 --> 00:16:33,150
And then over here you have five.

258
00:16:33,150 --> 00:16:37,320
Now DP at two two is this value over here which is three.

259
00:16:37,320 --> 00:16:40,950
So you have nine plus three over here which is 12.

260
00:16:40,950 --> 00:16:43,770
So the maximum between 3 and 12 is 12.

261
00:16:43,770 --> 00:16:45,900
So we will fill 12 over here.

262
00:16:47,110 --> 00:16:49,420
Now let's proceed to the next cell.

263
00:16:49,450 --> 00:16:56,980
Now for this exclude will have the value three and include is going to have the value nine plus depee

264
00:16:56,980 --> 00:16:57,580
at two.

265
00:16:57,580 --> 00:17:00,910
And then you have over here eight minus five.

266
00:17:00,910 --> 00:17:03,310
Because five is this weight over here.

267
00:17:03,310 --> 00:17:05,350
Now eight minus five is three.

268
00:17:05,350 --> 00:17:10,060
So deep at two and three is this value over here which is three.

269
00:17:10,060 --> 00:17:12,610
So nine plus three gives you 12.

270
00:17:12,610 --> 00:17:14,860
So you have three and 12.

271
00:17:14,860 --> 00:17:17,350
And the maximum between 3 and 12 is 12.

272
00:17:17,350 --> 00:17:19,240
So we fill 12 over here.

273
00:17:19,240 --> 00:17:21,880
And this is going to give us the answer.

274
00:17:21,880 --> 00:17:30,340
So the answer to this question is 12 which is the value in the DP table at index n w.

275
00:17:30,340 --> 00:17:32,110
So this is row n.

276
00:17:32,110 --> 00:17:34,900
And over here you have column w.

277
00:17:34,900 --> 00:17:39,430
So dp at n w gives us the answer.

278
00:17:39,430 --> 00:17:44,170
So this is the tabulation approach for solving the zero one knapsack problem.