In the previous video, we have discussed the recursive approach for solving the zero one knapsack problem.
Let's now go ahead and write the pseudocode for this approach.
So we would have a function let's call it knapsack, which we would recursively call again and again.
And within the function we have to write the base case.
And we have to write the recursive case.
So for the recursive case we can just make use of the choice diagram that we have previously discussed.
So for each item we would check whether the weight of that item is less than or equal to the remaining
capacity that can be added to the knapsack.
And if this is a yes, then we have two choices include or exclude.
If it's a no, we just have one choice which is to exclude.
And then finally we would have to return the maximum between include and exclude.
And when it comes to the base case, think of it as the last valid input or the first invalid input.
Now in this case the if let's say we are going from zero to n, so the last valid input would be the
last index, which if there are n items, the last valid index would be n minus one.
Or the first invalid input would be when you hit an index of n.
Now you can write it in the way that you would like to.
But again, this is the concept that you can use to come up with the base case.
You have one more thing to consider when you're writing the base case, which is if the remaining weight
that can be added.
If that's equal to zero, then you won't be able to add more items.
So that's again something that you need to include in the base case.
Now, if you're not hitting the base case, and let's say you've written the code for the choice diagram
that we have drawn over here, remember to return the maximum between exclude and include.
So this is a pseudocode for solving the zero one knapsack problem in a recursive manner.