Let's now get into the code and write the recursive solution that we have discussed in the previous
video.
So for this approach we will be needing a helper function.
Let me just call it helper itself.
And to this function we will be passing the index.
So again the index represents the item that we are considering to include into the knapsack okay.
So the index goes from zero up to n minus one because there are n items which are given to us.
And we also need to pass the remaining weight that can be added to the knapsack at that particular instance.
Now this is going to be the helper function.
Let's write the details later.
And finally we will be calling the helper function.
And we will be passing the index zero because we are considering the first item whether to include or
not include that particular item to the knapsack, and the remaining weight that can be added to the
knapsack at this point is equal to W, because nothing has been added to the knapsack so far.
Okay, and the helper function will return the maximum value that we can get by including various items
to the knapsack.
And because we are going to write it in a way that we get back the maximum value, we can just return
what we get back when we call the helper function the first time.
So this is the skeleton of the approach that we are going to take.
Now let's go ahead and write the details.
So over here we are going to write the base case as well as the recursive case.
All right.
Now the base case is going to be the scenario where the index that we are getting over here is greater
than equal to n, because that would be an invalid index.
Right.
Remember we had discussed that you can think of the base case as either the last valid input or the
first invalid input.
So if index.
Is greater than or equal to n, we are getting to the first invalid input, and because of that we have
hit the base case and we can return.
Okay, now there is one more possibility.
Now, if the remaining weight at any point that can be added to the knapsack is equal to zero, it would
mean that we would not be able to add more items to the knapsack.
And in that case also we can just return.
Okay.
So in these two cases we will be returning zero because that would be the additional value that can
get added to the knapsack if either of these cases has occurred, because no more value can be added
for the reasons that we have discussed.
All right.
So this is the base case.
Now as part of the recursive case we will have to calculate the exclude and include value okay.
Now exclude represents the case where we are not including the item at this particular index to the
knapsack and include would represent the scenario where, if possible, we include this particular item
that is the item at this particular index to the knapsack.
Now the exclude value is pretty straightforward.
To calculate, you just need to recursively call the helper function with a higher index, which is
index plus one, or the next index, and the remaining weight stays as it is because nothing has been
added to the knapsack.
Okay, so this over here would give us the exclude value.
Now when it comes to the include value, first we will assign zero to it because we are not always able
to include this particular item to the knapsack.
Okay.
So that's why initially we will assign the value zero to include because ultimately over here we are
going to return the maximum between exclude and include.
And therefore we would need something over here.
And that's why initially we said include to equal zero.
Now we proceed to the criteria.
So the criteria is weight at index has to be less than or equal to the remaining weight.
Only then we will be able to add this particular item to the knapsack.
So if this is true then we proceed.
And we say that include is equal to value at index because we have included the item at this particular
index to the knapsack.
So therefore the value in the knapsack has to increase by value at index right.
And then to this we will add helper index plus one and remaining weight minus weight at index.
Okay.
So what we are doing over here is we have added this particular item to the knapsack.
So therefore this value has increased.
And then we are calling the helper function recursively to add more items as possible to the knapsack.
So we are starting at index plus one.
And the remaining weight that can be added to the knapsack has been reduced by weighted index, because
this particular item has been added to the knapsack.
So that is it.
And then finally, as we have already written over here, because we have calculated, exclude and include
will just return the maximum between exclude and include.
So this is how we can solve this question.
Now notice that this is the recursive approach for solving the zero one knapsack problem.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
Now again do remember to make use of the user logs in case you are stuck and you want some help to debug
your code.
So over here for every test case you will find the input and the expected output and actual output for
that particular input.
And again if you want to add more console log statements you can do that.
So I've explained that in a previous lecture.
So you can just add console log statements.
And you need to call this function.
And you need to click run code.