Welcome back.
Let's now do a famous coding interview question, which is called the zero one knapsack problem.
Now let's read the question.
You are provided with a set of n items, each with a specified weight and value.
Your objective is to pack these items into a backpack with a weight limit of W, maximizing the total
value of items in the backpack.
Specifically, you have two arrays, so this is the value array representing the values of the items.
And you have the weight array indicating their weights.
So these are the indices from zero to n minus one.
Additionally you have a weight limit w for the backpack.
The challenge is to determine the most valuable combination of items where the total weight does not
exceed w.
Note that each item is unique and indivisible, meaning it must be either taken as a whole or left entirely.
So this is the question.
Now this is a variation of a problem called zero one knapsack problem.
Now, when it comes to knapsack problems, there are typically three common variations.
So the first one is the zero one knapsack over here.
And again a knapsack is just a backpack or a bag.
Now over here this is the zero one knapsack problem, because it's given that the items are unique and
indivisible.
So unique means you just have one item of a certain value and weight.
Now, if you could pack item one a multiple number of times into the bag, that would be a variation
of the knapsack problem called the unbounded knapsack.
Okay.
But over here it says the items are unique.
So you just have one set of each item.
And over here it's also mentioned that the items are indivisible.
So that means that you can't have half of an item added to the backpack.
So if the items were not indivisible, it would be another variation of the knapsack problem called
the fractional knapsack problem.
Now the fractional knapsack problem is not a dynamic programming problem.
This is something that's typically solved with the greedy approach.
So we have discussed the three common variations of the knapsack problem.
Over here we are dealing with the zero one knapsack problem.
Zero one indicates that you can either include an item which is the one over here, or you can exclude
an item from the bag, which is what the zero over here indicates.
And the items are indivisible and the items are unique.
Now, if the items were not unique, that's the variation of the knapsack problem called unbounded knapsack.
We will soon discuss that.
And then if the items were not indivisible, that's the variation of the knapsack problem called fractional
knapsack.
And we've discussed that this is solved using the greedy algorithmic approach.
Now let's get started with the zero one knapsack problem.
Now to understand this problem in a better manner, let's take an example.
Let's say n is equal to three.
And let's say the capacity of the knapsack is eight units or w is eight.
Now because n is equal to three we will have three items.
So let's say the value array is 239 and the weight array is 825.
So this means that the first item has a value of two and a weight of eight units.
The second item has a value of three and a weight of two units, and the third item has a value of nine
and a weight of five units.
Now you could, for example, just pick this single item because its weight itself is eight, and the
capacity of the knapsack is also eight.
So in this case, the value that you've been able to add to the knapsack is equal to two.
Now you could think of value as dollars or something like that.
So over here in this example the value achieved is two.
Now another approach would be to add these two items.
Notice that the sum of these two items weights respectively is two plus five, which is seven units,
which is still less than eight.
And the value at this point is three plus nine, which is equal to 12.
Okay.
And the question asks us to pack items into the knapsack or the backpack in a way that the value is
maximized.
So this is the question at hand.
And as always, remember to ask any clarifying questions that you may have when you are presented with
the coding interview question.
Now, a possible question over here is is it possible for n to be zero?
No.
Let's say the interviewer replies to you, no, that's not possible.
N will at least be one.
Now another question could be Will values be always be positive?
Or could it be the case that some items have negative values?
And let's say the interviewer replies that all the values are positive?
All right, so we have got a good idea of the question at hand.
Now let's go ahead and write a few test cases.
Now remember in coding interviews you can come up with test cases along with the interviewer.
And that's helpful to ensure that both of you are on the same page.
Now we've already seen one example where we had three items and the values were two, three, nine,
and the weights were eight, two, five.
In this case, the maximum value that can be added to the backpack or the knapsack is 12, which is
three plus nine.
So that's the required output in this case.
Let's take another example.
Let's say we just have two items.
The values are two and nine and the weights are ten and 11.
And the capacity of the backpack is just nine.
In this case, the output has to be zero because no item can be added to the backpack.
So we have understood the question and we have gone through a few test cases.
In the next video, let's try to think about how to solve this question.