When you are given a coding interview question, it's important to identify what approach could be taken
to solve the question at hand.
Now let's say you're given the zero one knapsack problem.
Now how do we identify that this is a dynamic programming question.
Now remember the two hints that we had discussed over here.
We can use those to identify that this is a DP question.
First you are presented with choices.
And the choices are like whether an item should be included and put in the backpack, or whether it
should be excluded and not included in the backpack.
So you have choices at hand, which indicates that you can probably use recursion to solve this question.
And again, we have discussed that one approach of dynamic programming is just recursion plus storage.
Another hint that you can use over here to identify that this is a DP question is that notice that you've
been asked an optimal solution, or you've been asked to maximize the value that can be added to the
knapsack.
So these hints can be used to identify that this is in fact a dynamic programming question.
And once you have identified this, remember not to directly start with the tabulation or bottom up
approach, because if it's a new question, it's very difficult to directly come up with the bottom
up approach.
It's much better to follow a step by step process where first you write the recursive approach, then
you memorize it, and then using your insights or things that you've understood from these two steps,
you will be able to successfully come up with the bottom up or tabulation approach.
And then finally, you can write the space optimized tabulation approach.
Remember, in many coding interview questions, it would be sufficient to come up with the memoization
approach.
And you can even stop at this point.
Now, if you approach DP questions in this manner or in these steps, you will be able to master dynamic
programming and learning things in this way will help you solve new problems as well.
And with new problems, I mean problems that you have never encountered previously.
So let's now get started with the recursive approach for solving the zero one knapsack problem.
Now to discuss the approach, let's take an example.
So we are given three items and the weight limit of the knapsack is given as eight.
Now, because we are dealing with recursion, we definitely have choices to make.
And let's think through these choices using a choice diagram.
So let's consider any one item.
Now what choices do I have with respect to this item?
Let's say the item is weight 1WT1 okay, so the choices that I have with respect to this item over here
is dependent on how much this weight is and what capacity is left that can be filled in the knapsack.
So if the weight of this item is less than or equal to the remaining capacity, if the weight over here
is less than or equal to the remaining capacity, then if if it's a yes, I have two choices.
I can either include this item in the backpack, or I can choose not to include it or exclude it from
the backpack.
Again, these choices are dependent on the criteria that my aim is to maximize the value added to the
backpack.
Now, if it's a no, if the weight is not less than or equal to the remaining capacity, then I just
have one choice, which is to exclude the item from the backpack.
Because if this is the case, if the weight is not less than or equal to the remaining capacity, I
cannot include the item.
So I have only one choice over here, which is to exclude.
So this is the choice diagram.
Now once you have this it's pretty straightforward to come up with the recursive approach.
So you just have to do this for each item given over here.
Now for going through all the items, you can either go from index zero till the last index.
In this case that's n minus one, or you can go from the last item to the first item.
Now we have discussed that you can write recursive solutions either going from zero to n or n to zero.
Now let's go ahead and draw the recursion tree for the recursive approach that we have discussed.
Let's again use the same example.
So we have three items.
The values are given over here.
The weights of the three items are given and the capacity of the knapsack is equal to eight.
Let's say over here we are going to draw the recursive tree going from the last index to the first index.
So we start with the last item over here.
And we have two choices for this.
We can either include this in the knapsack or we can exclude this in the knapsack.
Now, if we want to include this item and again we can include it because notice the weight is five.
And the remaining weight that can be added in the knapsack is eight.
At this point because nothing has been added to the knapsack.
So that's why we can include this item.
If we do include this item, the value which is already added to the knapsack is nine, and the remaining
weight that can be added would be eight minus five, which is equal to three, and the items that would
be left would be the remaining two items.
And the array for that would be two comma three and eight comma two.
Now again at this point to solve this subproblem.
Where these are the two arrays, and the weight that can be still added to the knapsack is three.
To solve this subproblem, we would again have two choices for the next item at hand, which is this
item over here.
So the two choices are either to include this item in the knapsack or to exclude this item from the
knapsack.
So if we were to include this item and notice we can include it, because this weight over here is two,
and the weight that can yet be added to the knapsack is three, so two is less than or equal to three.
That's why we can still include it.
So if we were to include it the value.
And again we're just dealing with this subproblem over here.
So three is the value that would be added to the knapsack, and the remaining weight would be three.
This three minus two which is equal to one.
And then we just have one more item to consider for adding to the knapsack.
And again, once we are over here to solve this subproblem over here, where the remaining weight that
can be added is one unit, and this is the single item which is there for consideration.
Notice over here we cannot include it because eight is not less than or equal to one, and the only
option is to exclude it.
Now when we exclude it, there is no addition to the value.
So the value is just going to be equal to zero when we exclude over here.
Now for this case also when we exclude we are not including this item.
So again the weight which still can be added would remain at three.
And we would just have one more item for consideration.
So the subproblem becomes two and then eight.
And the remaining weight is three.
And for this subproblem.
We have two choices, which is to include or exclude.
But because eight is not less than or equal to three, we cannot include it.
And our only option is to exclude.
And when we exclude, the value just becomes zero.
Now let's proceed and complete this branch over here.
So when we are considering the first item and if we exclude it, the weight that can be added to the
knapsack remains eight itself.
And we would just have two more items for consideration.
So the subproblem becomes two comma three and eight comma two.
And the weight is eight.
Now to solve this subproblem again we have two choices which is to either include or exclude this item
over here okay.
So at index one.
So we have two choices include or exclude.
Notice that two which is the weight is less than or equal to eight.
That's why there is a possibility to include the item in the knapsack.
If we do include it the value becomes three.
So the problem changes to three plus.
Two and eight.
You just have one more item for consideration, and the remaining weight that can be added would be
eight minus two, which is equal to six.
Now to solve this subproblem over here where w is six and you just have one item for consideration,
you have two choices which are either to include this item or to exclude this item.
But over here, because eight is not less than or equal to six, we cannot include it.
And our only option is to exclude it.
And when we exclude it, the value is just zero.
Now let's complete this branch over here.
Now we were considering this item and if we exclude it, the value does not increase and the subproblem
becomes two and eight will just have one more item left and the weight remains as eight itself.
Now, when we are trying to solve this sub problem, we have two choices, which is to include or exclude.
And because eight is less than or equal to eight, we can include it.
So if we include it, the value becomes two plus.
And then you have no more element.
And if you exclude it the value just becomes zero.
So this is the recursion tree for the zero one knapsack problem.
Now let's see how the algorithm would solve this problem.
So we would start with this element.
And we come let's say to the include branch.
And we come to nine plus this subproblem over here.
And this would again recursively call the function that we are writing to identify the value for the
include case.
And we would come to this part which has this sub problem.
And then notice that this sub problem is the maximum between include and exclude.
Because we are not calling the include branch, we would be setting this to zero, and the exclude branch
also has the value zero.
So the maximum between 0 and 0 will be zero itself.
So that's why this subproblem over here will have the value zero.
So this is going to be equal to zero.
And three plus zero is three itself.
Now what about the exclude branch over here.
Now over here again notice that when we're trying to solve this subproblem we have the include branch
which was not executed because including this item was not possible.
So we set include to zero.
And the exclude branch also has the value zero.
So the maximum between 0 and 0 is zero itself.
So the value of this subproblem over here becomes zero.
So this is zero.
So the include branch has the value three plus zero, which is three, and the exclude branch has the
value zero.
So the maximum between 3 and 0 is three.
So this subproblem over here becomes three okay.
Now we have the value for this include as nine plus three which is 12.
So we have 12 over here.
Now the algorithm would proceed and try to find the exclude value.
So we come over here and then we come over here to the include branch.
And over here we have this subproblem three plus this subproblem.
And when we're trying to find the value of this subproblem notice we are not able to include.
So we set it to zero.
And the value of exclude is zero.
So the maximum between 0 and 0 is zero itself.
So this over here becomes zero.
And three plus zero is three.
So the value of include over here is three.
And then it comes to solve the exclude branch.
So the value of this sub problem over here becomes two.
Right.
Because over here notice you are having two as the value.
Because when you're trying to again call the recursive function for no item, which is this case that
would just return zero.
So this will become two two plus zero which is two itself.
And over here the exclude scenario has a value of zero.
So the maximum between 2 and 0 is two.
So the value of this over here will become two.
So the value of include is three plus zero, which is three, and the value of exclude is two.
So the maximum between 3 and 2 is three.
So the value of this over here is going to be three.
All right.
So include at this point is 12.
And exclude is three.
So the maximum between 12 and 3 is 12.
So that's how the algorithm would solve it.
And it would identify the maximum value that can be added as 12.