1
00:00:01,560 --> 00:00:08,790
When you are given a coding interview question, it's important to identify what approach could be taken

2
00:00:08,790 --> 00:00:10,500
to solve the question at hand.

3
00:00:10,530 --> 00:00:14,220
Now let's say you're given the zero one knapsack problem.

4
00:00:14,220 --> 00:00:18,240
Now how do we identify that this is a dynamic programming question.

5
00:00:18,270 --> 00:00:22,200
Now remember the two hints that we had discussed over here.

6
00:00:22,200 --> 00:00:25,590
We can use those to identify that this is a DP question.

7
00:00:25,590 --> 00:00:28,230
First you are presented with choices.

8
00:00:28,230 --> 00:00:34,590
And the choices are like whether an item should be included and put in the backpack, or whether it

9
00:00:34,590 --> 00:00:37,620
should be excluded and not included in the backpack.

10
00:00:37,620 --> 00:00:43,380
So you have choices at hand, which indicates that you can probably use recursion to solve this question.

11
00:00:43,380 --> 00:00:49,050
And again, we have discussed that one approach of dynamic programming is just recursion plus storage.

12
00:00:49,530 --> 00:00:56,250
Another hint that you can use over here to identify that this is a DP question is that notice that you've

13
00:00:56,250 --> 00:01:03,090
been asked an optimal solution, or you've been asked to maximize the value that can be added to the

14
00:01:03,090 --> 00:01:03,750
knapsack.

15
00:01:03,750 --> 00:01:09,870
So these hints can be used to identify that this is in fact a dynamic programming question.

16
00:01:09,870 --> 00:01:17,400
And once you have identified this, remember not to directly start with the tabulation or bottom up

17
00:01:17,400 --> 00:01:22,950
approach, because if it's a new question, it's very difficult to directly come up with the bottom

18
00:01:22,950 --> 00:01:23,640
up approach.

19
00:01:23,640 --> 00:01:30,510
It's much better to follow a step by step process where first you write the recursive approach, then

20
00:01:30,510 --> 00:01:36,630
you memorize it, and then using your insights or things that you've understood from these two steps,

21
00:01:36,630 --> 00:01:41,340
you will be able to successfully come up with the bottom up or tabulation approach.

22
00:01:41,340 --> 00:01:45,360
And then finally, you can write the space optimized tabulation approach.

23
00:01:45,360 --> 00:01:51,750
Remember, in many coding interview questions, it would be sufficient to come up with the memoization

24
00:01:51,750 --> 00:01:52,230
approach.

25
00:01:52,230 --> 00:01:54,360
And you can even stop at this point.

26
00:01:54,360 --> 00:02:03,900
Now, if you approach DP questions in this manner or in these steps, you will be able to master dynamic

27
00:02:03,900 --> 00:02:09,900
programming and learning things in this way will help you solve new problems as well.

28
00:02:09,900 --> 00:02:14,640
And with new problems, I mean problems that you have never encountered previously.

29
00:02:14,640 --> 00:02:20,700
So let's now get started with the recursive approach for solving the zero one knapsack problem.

30
00:02:21,120 --> 00:02:24,360
Now to discuss the approach, let's take an example.

31
00:02:24,360 --> 00:02:30,450
So we are given three items and the weight limit of the knapsack is given as eight.

32
00:02:30,540 --> 00:02:35,880
Now, because we are dealing with recursion, we definitely have choices to make.

33
00:02:35,880 --> 00:02:39,960
And let's think through these choices using a choice diagram.

34
00:02:39,960 --> 00:02:43,350
So let's consider any one item.

35
00:02:43,350 --> 00:02:47,970
Now what choices do I have with respect to this item?

36
00:02:47,970 --> 00:02:57,240
Let's say the item is weight 1WT1 okay, so the choices that I have with respect to this item over here

37
00:02:57,240 --> 00:03:05,760
is dependent on how much this weight is and what capacity is left that can be filled in the knapsack.

38
00:03:05,760 --> 00:03:13,860
So if the weight of this item is less than or equal to the remaining capacity, if the weight over here

39
00:03:13,860 --> 00:03:20,490
is less than or equal to the remaining capacity, then if if it's a yes, I have two choices.

40
00:03:20,490 --> 00:03:28,470
I can either include this item in the backpack, or I can choose not to include it or exclude it from

41
00:03:28,470 --> 00:03:29,220
the backpack.

42
00:03:29,220 --> 00:03:36,390
Again, these choices are dependent on the criteria that my aim is to maximize the value added to the

43
00:03:36,390 --> 00:03:37,110
backpack.

44
00:03:37,110 --> 00:03:45,450
Now, if it's a no, if the weight is not less than or equal to the remaining capacity, then I just

45
00:03:45,450 --> 00:03:50,100
have one choice, which is to exclude the item from the backpack.

46
00:03:50,100 --> 00:03:55,770
Because if this is the case, if the weight is not less than or equal to the remaining capacity, I

47
00:03:55,770 --> 00:03:57,060
cannot include the item.

48
00:03:57,060 --> 00:04:00,300
So I have only one choice over here, which is to exclude.

49
00:04:00,300 --> 00:04:02,280
So this is the choice diagram.

50
00:04:02,280 --> 00:04:07,650
Now once you have this it's pretty straightforward to come up with the recursive approach.

51
00:04:07,890 --> 00:04:11,910
So you just have to do this for each item given over here.

52
00:04:11,910 --> 00:04:19,140
Now for going through all the items, you can either go from index zero till the last index.

53
00:04:19,140 --> 00:04:24,900
In this case that's n minus one, or you can go from the last item to the first item.

54
00:04:24,900 --> 00:04:31,350
Now we have discussed that you can write recursive solutions either going from zero to n or n to zero.

55
00:04:31,350 --> 00:04:37,710
Now let's go ahead and draw the recursion tree for the recursive approach that we have discussed.

56
00:04:37,710 --> 00:04:39,780
Let's again use the same example.

57
00:04:39,780 --> 00:04:41,400
So we have three items.

58
00:04:41,400 --> 00:04:43,020
The values are given over here.

59
00:04:43,020 --> 00:04:48,690
The weights of the three items are given and the capacity of the knapsack is equal to eight.

60
00:04:48,690 --> 00:04:55,440
Let's say over here we are going to draw the recursive tree going from the last index to the first index.

61
00:04:55,440 --> 00:04:58,440
So we start with the last item over here.

62
00:04:58,440 --> 00:05:01,110
And we have two choices for this.

63
00:05:01,440 --> 00:05:07,500
We can either include this in the knapsack or we can exclude this in the knapsack.

64
00:05:07,530 --> 00:05:14,220
Now, if we want to include this item and again we can include it because notice the weight is five.

65
00:05:14,220 --> 00:05:17,670
And the remaining weight that can be added in the knapsack is eight.

66
00:05:17,670 --> 00:05:21,000
At this point because nothing has been added to the knapsack.

67
00:05:21,000 --> 00:05:23,700
So that's why we can include this item.

68
00:05:23,700 --> 00:05:31,710
If we do include this item, the value which is already added to the knapsack is nine, and the remaining

69
00:05:31,710 --> 00:05:39,240
weight that can be added would be eight minus five, which is equal to three, and the items that would

70
00:05:39,240 --> 00:05:42,210
be left would be the remaining two items.

71
00:05:42,210 --> 00:05:46,050
And the array for that would be two comma three and eight comma two.

72
00:05:46,080 --> 00:05:49,620
Now again at this point to solve this subproblem.

73
00:05:50,560 --> 00:05:56,290
Where these are the two arrays, and the weight that can be still added to the knapsack is three.

74
00:05:56,320 --> 00:06:02,710
To solve this subproblem, we would again have two choices for the next item at hand, which is this

75
00:06:02,710 --> 00:06:03,700
item over here.

76
00:06:04,810 --> 00:06:11,410
So the two choices are either to include this item in the knapsack or to exclude this item from the

77
00:06:11,410 --> 00:06:12,220
knapsack.

78
00:06:12,640 --> 00:06:20,110
So if we were to include this item and notice we can include it, because this weight over here is two,

79
00:06:20,110 --> 00:06:25,720
and the weight that can yet be added to the knapsack is three, so two is less than or equal to three.

80
00:06:25,720 --> 00:06:27,730
That's why we can still include it.

81
00:06:27,730 --> 00:06:30,730
So if we were to include it the value.

82
00:06:30,730 --> 00:06:33,460
And again we're just dealing with this subproblem over here.

83
00:06:34,120 --> 00:06:40,780
So three is the value that would be added to the knapsack, and the remaining weight would be three.

84
00:06:40,780 --> 00:06:43,360
This three minus two which is equal to one.

85
00:06:43,360 --> 00:06:48,160
And then we just have one more item to consider for adding to the knapsack.

86
00:06:48,160 --> 00:06:54,670
And again, once we are over here to solve this subproblem over here, where the remaining weight that

87
00:06:54,670 --> 00:07:00,190
can be added is one unit, and this is the single item which is there for consideration.

88
00:07:00,190 --> 00:07:06,850
Notice over here we cannot include it because eight is not less than or equal to one, and the only

89
00:07:06,850 --> 00:07:08,680
option is to exclude it.

90
00:07:08,680 --> 00:07:11,980
Now when we exclude it, there is no addition to the value.

91
00:07:11,980 --> 00:07:15,460
So the value is just going to be equal to zero when we exclude over here.

92
00:07:15,460 --> 00:07:21,040
Now for this case also when we exclude we are not including this item.

93
00:07:21,040 --> 00:07:26,080
So again the weight which still can be added would remain at three.

94
00:07:26,080 --> 00:07:29,110
And we would just have one more item for consideration.

95
00:07:29,110 --> 00:07:32,140
So the subproblem becomes two and then eight.

96
00:07:32,140 --> 00:07:33,760
And the remaining weight is three.

97
00:07:33,760 --> 00:07:35,680
And for this subproblem.

98
00:07:36,330 --> 00:07:39,930
We have two choices, which is to include or exclude.

99
00:07:39,930 --> 00:07:44,370
But because eight is not less than or equal to three, we cannot include it.

100
00:07:44,370 --> 00:07:46,860
And our only option is to exclude.

101
00:07:46,860 --> 00:07:50,760
And when we exclude, the value just becomes zero.

102
00:07:50,790 --> 00:07:53,910
Now let's proceed and complete this branch over here.

103
00:07:53,910 --> 00:08:00,210
So when we are considering the first item and if we exclude it, the weight that can be added to the

104
00:08:00,210 --> 00:08:02,310
knapsack remains eight itself.

105
00:08:02,310 --> 00:08:06,210
And we would just have two more items for consideration.

106
00:08:06,210 --> 00:08:09,930
So the subproblem becomes two comma three and eight comma two.

107
00:08:09,930 --> 00:08:11,580
And the weight is eight.

108
00:08:11,610 --> 00:08:19,080
Now to solve this subproblem again we have two choices which is to either include or exclude this item

109
00:08:19,080 --> 00:08:20,490
over here okay.

110
00:08:20,490 --> 00:08:21,750
So at index one.

111
00:08:21,750 --> 00:08:24,780
So we have two choices include or exclude.

112
00:08:24,780 --> 00:08:28,800
Notice that two which is the weight is less than or equal to eight.

113
00:08:28,800 --> 00:08:33,330
That's why there is a possibility to include the item in the knapsack.

114
00:08:33,330 --> 00:08:36,420
If we do include it the value becomes three.

115
00:08:36,420 --> 00:08:39,570
So the problem changes to three plus.

116
00:08:40,640 --> 00:08:41,540
Two and eight.

117
00:08:41,540 --> 00:08:46,730
You just have one more item for consideration, and the remaining weight that can be added would be

118
00:08:46,730 --> 00:08:49,700
eight minus two, which is equal to six.

119
00:08:49,700 --> 00:08:56,570
Now to solve this subproblem over here where w is six and you just have one item for consideration,

120
00:08:56,570 --> 00:09:02,600
you have two choices which are either to include this item or to exclude this item.

121
00:09:02,600 --> 00:09:08,240
But over here, because eight is not less than or equal to six, we cannot include it.

122
00:09:08,240 --> 00:09:10,850
And our only option is to exclude it.

123
00:09:10,850 --> 00:09:13,670
And when we exclude it, the value is just zero.

124
00:09:13,670 --> 00:09:16,250
Now let's complete this branch over here.

125
00:09:16,250 --> 00:09:23,330
Now we were considering this item and if we exclude it, the value does not increase and the subproblem

126
00:09:23,330 --> 00:09:29,120
becomes two and eight will just have one more item left and the weight remains as eight itself.

127
00:09:30,410 --> 00:09:37,070
Now, when we are trying to solve this sub problem, we have two choices, which is to include or exclude.

128
00:09:37,070 --> 00:09:41,930
And because eight is less than or equal to eight, we can include it.

129
00:09:41,930 --> 00:09:45,080
So if we include it, the value becomes two plus.

130
00:09:45,080 --> 00:09:47,150
And then you have no more element.

131
00:09:47,150 --> 00:09:50,480
And if you exclude it the value just becomes zero.

132
00:09:50,480 --> 00:09:54,980
So this is the recursion tree for the zero one knapsack problem.

133
00:09:54,980 --> 00:09:57,890
Now let's see how the algorithm would solve this problem.

134
00:09:57,890 --> 00:10:00,200
So we would start with this element.

135
00:10:00,200 --> 00:10:02,930
And we come let's say to the include branch.

136
00:10:02,930 --> 00:10:06,650
And we come to nine plus this subproblem over here.

137
00:10:07,280 --> 00:10:13,460
And this would again recursively call the function that we are writing to identify the value for the

138
00:10:13,460 --> 00:10:14,450
include case.

139
00:10:14,450 --> 00:10:18,260
And we would come to this part which has this sub problem.

140
00:10:18,260 --> 00:10:23,660
And then notice that this sub problem is the maximum between include and exclude.

141
00:10:23,660 --> 00:10:29,300
Because we are not calling the include branch, we would be setting this to zero, and the exclude branch

142
00:10:29,300 --> 00:10:30,710
also has the value zero.

143
00:10:30,710 --> 00:10:34,790
So the maximum between 0 and 0 will be zero itself.

144
00:10:34,790 --> 00:10:39,410
So that's why this subproblem over here will have the value zero.

145
00:10:40,570 --> 00:10:42,520
So this is going to be equal to zero.

146
00:10:42,730 --> 00:10:46,000
And three plus zero is three itself.

147
00:10:46,000 --> 00:10:48,580
Now what about the exclude branch over here.

148
00:10:49,090 --> 00:10:55,750
Now over here again notice that when we're trying to solve this subproblem we have the include branch

149
00:10:55,750 --> 00:11:01,600
which was not executed because including this item was not possible.

150
00:11:01,600 --> 00:11:03,520
So we set include to zero.

151
00:11:03,520 --> 00:11:06,370
And the exclude branch also has the value zero.

152
00:11:06,370 --> 00:11:09,250
So the maximum between 0 and 0 is zero itself.

153
00:11:09,250 --> 00:11:12,880
So the value of this subproblem over here becomes zero.

154
00:11:14,420 --> 00:11:15,560
So this is zero.

155
00:11:16,750 --> 00:11:22,810
So the include branch has the value three plus zero, which is three, and the exclude branch has the

156
00:11:22,810 --> 00:11:23,830
value zero.

157
00:11:23,830 --> 00:11:27,010
So the maximum between 3 and 0 is three.

158
00:11:27,010 --> 00:11:31,330
So this subproblem over here becomes three okay.

159
00:11:31,330 --> 00:11:36,070
Now we have the value for this include as nine plus three which is 12.

160
00:11:36,070 --> 00:11:37,540
So we have 12 over here.

161
00:11:37,540 --> 00:11:41,980
Now the algorithm would proceed and try to find the exclude value.

162
00:11:41,980 --> 00:11:46,240
So we come over here and then we come over here to the include branch.

163
00:11:46,240 --> 00:11:50,230
And over here we have this subproblem three plus this subproblem.

164
00:11:50,230 --> 00:11:54,940
And when we're trying to find the value of this subproblem notice we are not able to include.

165
00:11:54,940 --> 00:11:56,320
So we set it to zero.

166
00:11:56,320 --> 00:11:58,060
And the value of exclude is zero.

167
00:11:58,060 --> 00:12:01,570
So the maximum between 0 and 0 is zero itself.

168
00:12:02,490 --> 00:12:05,460
So this over here becomes zero.

169
00:12:07,250 --> 00:12:09,380
And three plus zero is three.

170
00:12:09,380 --> 00:12:11,720
So the value of include over here is three.

171
00:12:11,720 --> 00:12:14,510
And then it comes to solve the exclude branch.

172
00:12:14,510 --> 00:12:18,530
So the value of this sub problem over here becomes two.

173
00:12:18,530 --> 00:12:18,860
Right.

174
00:12:18,860 --> 00:12:22,040
Because over here notice you are having two as the value.

175
00:12:22,580 --> 00:12:28,340
Because when you're trying to again call the recursive function for no item, which is this case that

176
00:12:28,340 --> 00:12:29,540
would just return zero.

177
00:12:29,540 --> 00:12:32,990
So this will become two two plus zero which is two itself.

178
00:12:32,990 --> 00:12:36,770
And over here the exclude scenario has a value of zero.

179
00:12:36,770 --> 00:12:39,800
So the maximum between 2 and 0 is two.

180
00:12:39,830 --> 00:12:42,920
So the value of this over here will become two.

181
00:12:44,580 --> 00:12:50,070
So the value of include is three plus zero, which is three, and the value of exclude is two.

182
00:12:50,100 --> 00:12:52,830
So the maximum between 3 and 2 is three.

183
00:12:52,830 --> 00:12:56,220
So the value of this over here is going to be three.

184
00:12:58,670 --> 00:12:59,120
All right.

185
00:12:59,120 --> 00:13:02,150
So include at this point is 12.

186
00:13:02,690 --> 00:13:04,400
And exclude is three.

187
00:13:04,400 --> 00:13:07,580
So the maximum between 12 and 3 is 12.

188
00:13:07,580 --> 00:13:09,860
So that's how the algorithm would solve it.

189
00:13:09,860 --> 00:13:14,630
And it would identify the maximum value that can be added as 12.