1
00:00:00,110 --> 00:00:06,620
In the previous video, we have discussed the recursive approach for solving the zero one knapsack problem.

2
00:00:06,650 --> 00:00:10,640
Let's now go ahead and write the pseudocode for this approach.

3
00:00:10,640 --> 00:00:16,910
So we would have a function let's call it knapsack, which we would recursively call again and again.

4
00:00:16,910 --> 00:00:20,240
And within the function we have to write the base case.

5
00:00:20,240 --> 00:00:22,640
And we have to write the recursive case.

6
00:00:22,640 --> 00:00:29,840
So for the recursive case we can just make use of the choice diagram that we have previously discussed.

7
00:00:29,840 --> 00:00:36,320
So for each item we would check whether the weight of that item is less than or equal to the remaining

8
00:00:36,320 --> 00:00:39,050
capacity that can be added to the knapsack.

9
00:00:39,050 --> 00:00:43,910
And if this is a yes, then we have two choices include or exclude.

10
00:00:43,910 --> 00:00:47,360
If it's a no, we just have one choice which is to exclude.

11
00:00:47,360 --> 00:00:52,730
And then finally we would have to return the maximum between include and exclude.

12
00:00:52,730 --> 00:01:01,790
And when it comes to the base case, think of it as the last valid input or the first invalid input.

13
00:01:01,790 --> 00:01:09,890
Now in this case the if let's say we are going from zero to n, so the last valid input would be the

14
00:01:09,890 --> 00:01:15,350
last index, which if there are n items, the last valid index would be n minus one.

15
00:01:15,350 --> 00:01:19,790
Or the first invalid input would be when you hit an index of n.

16
00:01:19,790 --> 00:01:22,580
Now you can write it in the way that you would like to.

17
00:01:22,580 --> 00:01:26,150
But again, this is the concept that you can use to come up with the base case.

18
00:01:26,150 --> 00:01:31,220
You have one more thing to consider when you're writing the base case, which is if the remaining weight

19
00:01:31,220 --> 00:01:32,420
that can be added.

20
00:01:32,420 --> 00:01:37,100
If that's equal to zero, then you won't be able to add more items.

21
00:01:37,100 --> 00:01:40,940
So that's again something that you need to include in the base case.

22
00:01:41,210 --> 00:01:46,880
Now, if you're not hitting the base case, and let's say you've written the code for the choice diagram

23
00:01:46,880 --> 00:01:53,210
that we have drawn over here, remember to return the maximum between exclude and include.

24
00:01:53,210 --> 00:01:58,940
So this is a pseudocode for solving the zero one knapsack problem in a recursive manner.