1
00:00:00,110 --> 00:00:04,970
Let's now get into the code and write the recursive solution that we have discussed in the previous

2
00:00:04,970 --> 00:00:05,420
video.

3
00:00:05,420 --> 00:00:08,990
So for this approach we will be needing a helper function.

4
00:00:08,990 --> 00:00:11,330
Let me just call it helper itself.

5
00:00:11,330 --> 00:00:14,990
And to this function we will be passing the index.

6
00:00:14,990 --> 00:00:21,230
So again the index represents the item that we are considering to include into the knapsack okay.

7
00:00:21,230 --> 00:00:27,230
So the index goes from zero up to n minus one because there are n items which are given to us.

8
00:00:27,230 --> 00:00:34,460
And we also need to pass the remaining weight that can be added to the knapsack at that particular instance.

9
00:00:34,490 --> 00:00:36,560
Now this is going to be the helper function.

10
00:00:36,560 --> 00:00:38,720
Let's write the details later.

11
00:00:38,720 --> 00:00:41,360
And finally we will be calling the helper function.

12
00:00:41,360 --> 00:00:47,090
And we will be passing the index zero because we are considering the first item whether to include or

13
00:00:47,090 --> 00:00:52,400
not include that particular item to the knapsack, and the remaining weight that can be added to the

14
00:00:52,400 --> 00:00:57,800
knapsack at this point is equal to W, because nothing has been added to the knapsack so far.

15
00:00:57,800 --> 00:01:06,320
Okay, and the helper function will return the maximum value that we can get by including various items

16
00:01:06,320 --> 00:01:07,190
to the knapsack.

17
00:01:07,190 --> 00:01:12,770
And because we are going to write it in a way that we get back the maximum value, we can just return

18
00:01:12,770 --> 00:01:16,250
what we get back when we call the helper function the first time.

19
00:01:16,250 --> 00:01:19,820
So this is the skeleton of the approach that we are going to take.

20
00:01:19,820 --> 00:01:21,950
Now let's go ahead and write the details.

21
00:01:21,950 --> 00:01:27,650
So over here we are going to write the base case as well as the recursive case.

22
00:01:29,020 --> 00:01:29,530
All right.

23
00:01:29,560 --> 00:01:36,220
Now the base case is going to be the scenario where the index that we are getting over here is greater

24
00:01:36,220 --> 00:01:39,820
than equal to n, because that would be an invalid index.

25
00:01:39,820 --> 00:01:40,090
Right.

26
00:01:40,090 --> 00:01:46,270
Remember we had discussed that you can think of the base case as either the last valid input or the

27
00:01:46,270 --> 00:01:47,590
first invalid input.

28
00:01:47,590 --> 00:01:49,660
So if index.

29
00:01:50,610 --> 00:01:57,390
Is greater than or equal to n, we are getting to the first invalid input, and because of that we have

30
00:01:57,390 --> 00:01:59,310
hit the base case and we can return.

31
00:01:59,310 --> 00:02:01,560
Okay, now there is one more possibility.

32
00:02:01,560 --> 00:02:07,950
Now, if the remaining weight at any point that can be added to the knapsack is equal to zero, it would

33
00:02:07,950 --> 00:02:11,460
mean that we would not be able to add more items to the knapsack.

34
00:02:11,460 --> 00:02:14,430
And in that case also we can just return.

35
00:02:14,430 --> 00:02:14,820
Okay.

36
00:02:14,820 --> 00:02:20,700
So in these two cases we will be returning zero because that would be the additional value that can

37
00:02:20,700 --> 00:02:26,940
get added to the knapsack if either of these cases has occurred, because no more value can be added

38
00:02:26,940 --> 00:02:28,650
for the reasons that we have discussed.

39
00:02:28,980 --> 00:02:29,400
All right.

40
00:02:29,400 --> 00:02:30,840
So this is the base case.

41
00:02:30,840 --> 00:02:38,160
Now as part of the recursive case we will have to calculate the exclude and include value okay.

42
00:02:38,160 --> 00:02:45,750
Now exclude represents the case where we are not including the item at this particular index to the

43
00:02:45,750 --> 00:02:52,050
knapsack and include would represent the scenario where, if possible, we include this particular item

44
00:02:52,050 --> 00:02:55,380
that is the item at this particular index to the knapsack.

45
00:02:55,380 --> 00:02:58,470
Now the exclude value is pretty straightforward.

46
00:02:58,470 --> 00:03:03,540
To calculate, you just need to recursively call the helper function with a higher index, which is

47
00:03:03,540 --> 00:03:09,270
index plus one, or the next index, and the remaining weight stays as it is because nothing has been

48
00:03:09,270 --> 00:03:10,380
added to the knapsack.

49
00:03:10,380 --> 00:03:13,980
Okay, so this over here would give us the exclude value.

50
00:03:13,980 --> 00:03:21,030
Now when it comes to the include value, first we will assign zero to it because we are not always able

51
00:03:21,030 --> 00:03:23,700
to include this particular item to the knapsack.

52
00:03:23,700 --> 00:03:24,090
Okay.

53
00:03:24,090 --> 00:03:29,730
So that's why initially we will assign the value zero to include because ultimately over here we are

54
00:03:29,730 --> 00:03:34,830
going to return the maximum between exclude and include.

55
00:03:37,090 --> 00:03:39,850
And therefore we would need something over here.

56
00:03:39,850 --> 00:03:43,330
And that's why initially we said include to equal zero.

57
00:03:43,360 --> 00:03:45,310
Now we proceed to the criteria.

58
00:03:45,310 --> 00:03:52,450
So the criteria is weight at index has to be less than or equal to the remaining weight.

59
00:03:52,690 --> 00:03:57,460
Only then we will be able to add this particular item to the knapsack.

60
00:03:57,460 --> 00:04:01,000
So if this is true then we proceed.

61
00:04:01,000 --> 00:04:09,190
And we say that include is equal to value at index because we have included the item at this particular

62
00:04:09,190 --> 00:04:10,600
index to the knapsack.

63
00:04:10,600 --> 00:04:16,030
So therefore the value in the knapsack has to increase by value at index right.

64
00:04:16,030 --> 00:04:29,020
And then to this we will add helper index plus one and remaining weight minus weight at index.

65
00:04:30,350 --> 00:04:30,890
Okay.

66
00:04:30,890 --> 00:04:35,330
So what we are doing over here is we have added this particular item to the knapsack.

67
00:04:35,330 --> 00:04:37,580
So therefore this value has increased.

68
00:04:37,580 --> 00:04:44,030
And then we are calling the helper function recursively to add more items as possible to the knapsack.

69
00:04:44,030 --> 00:04:46,280
So we are starting at index plus one.

70
00:04:46,280 --> 00:04:52,730
And the remaining weight that can be added to the knapsack has been reduced by weighted index, because

71
00:04:52,730 --> 00:04:55,760
this particular item has been added to the knapsack.

72
00:04:55,760 --> 00:04:56,720
So that is it.

73
00:04:56,720 --> 00:05:02,300
And then finally, as we have already written over here, because we have calculated, exclude and include

74
00:05:02,300 --> 00:05:06,380
will just return the maximum between exclude and include.

75
00:05:06,380 --> 00:05:08,720
So this is how we can solve this question.

76
00:05:08,720 --> 00:05:13,400
Now notice that this is the recursive approach for solving the zero one knapsack problem.

77
00:05:13,400 --> 00:05:17,630
Now let's go ahead and run this code and see if it's passing all the test cases.

78
00:05:18,410 --> 00:05:20,090
And you can see that it's working.

79
00:05:20,090 --> 00:05:21,890
It's passing all the test cases.

80
00:05:21,890 --> 00:05:28,070
Now again do remember to make use of the user logs in case you are stuck and you want some help to debug

81
00:05:28,070 --> 00:05:28,670
your code.

82
00:05:28,670 --> 00:05:35,780
So over here for every test case you will find the input and the expected output and actual output for

83
00:05:35,810 --> 00:05:36,950
that particular input.

84
00:05:36,950 --> 00:05:41,060
And again if you want to add more console log statements you can do that.

85
00:05:41,060 --> 00:05:43,250
So I've explained that in a previous lecture.

86
00:05:43,250 --> 00:05:45,530
So you can just add console log statements.

87
00:05:45,530 --> 00:05:47,300
And you need to call this function.

88
00:05:47,300 --> 00:05:49,040
And you need to click run code.