Welcome back.
In the previous videos we have got ourselves introduced to the greedy algorithmic approach.
Now let's get started with a few interesting coding interview questions.
So over here we have a beautiful question which is the fractional knapsack problem.
Previously under dynamic programming, we have already discussed the zero one knapsack problem and the
unbounded knapsack problem.
So let's get started with this question.
Over here.
The question reads determine how to optimally fill a knapsack with a capacity of w kilograms, using
a list of n items where each item is represented by a pair profit comma weight.
In the fractional knapsack problem, you can take fractions of items to maximize the total profit in
the knapsack, and then it's mentioned n will be greater than equal to one, which means that you will
not be given an array which has nothing in it.
Okay, so that's mentioned in the question.
And therefore we don't need to account for it explicitly in our solution.
So that's all that this line over here gives.
Now we are also given an example.
So let's take a look at the example to thoroughly understand this question.
So we are given this array over here.
And we can see that it has three elements okay.
So this is item one.
This is item two and this is item three.
And we know that each of these pairs represent the profit and the weight of the item.
So item one if added to the knapsack would increase the profit by 70 and the weight by ten.
And also notice in the question it says that you can take fractions of items okay.
So if you take the whole item one then the profit added to the knapsack would be 70.
And if you add, let's say one tenth of this item, okay.
If you add one tenth of this item, then the profit added to the knapsack also would be one tenth of
70, which is equal to seven.
So this is just to understand the question.
So again we have these three items.
And in the first scenario over here it's given that w is equal to 25 which means that the knapsack has
a capacity of 25kg.
And the expected output in this case is equal to 145.
And for this you can take the whole of item one okay.
So that would add ten kilograms.
And you can take half of item three which would add 15kg.
And the total in this case would be ten plus 15 which is 25.
And when you add the whole of item one you are increasing the profit by 70.
And when you're taking only half of item three, you are increasing the profit by half of 150, which
is 75 and 70 plus 75 gives us 145.
Okay.
And again, this is the best way in which the knapsack can be filled.
Like for example, you could add ten over here and then you're left with 15.
And you could take 15 from item two as well.
And if you do that what would be the profit?
The profit would be 70 plus 15 out of 20 into 90 okay.
And this would simplify to.
15 into 4.5 plus 70, which is equal to 70 plus 67.5 okay.
And this definitely is lower than 70 plus 75.
So again that's the example given to us.
And we have one more example.
If the capacity of the knapsack was equal to 45 kilogram, then the expected output would be 240 2.5,
which can be achieved by taking ten kilograms of item one.
And then you have five kilograms of item two and 30kg of item three.
Okay.
And because you're taking the whole of item one, the profit increases by 70.
You're taking the whole of item three.
So the profit increases by 150.
And you're taking five kilogram of item two.
And therefore the profit would increase by 90 into five by 20.
Okay.
And five by 20 is one by four.
So that's how you get 90 by four over here.
And when you add all of these up you get 240 2.5, which is the maximum profit or the maximum value
that you can add to the knapsack when the input array is this array over here.
Okay.
So this is the question over here.
Again to summarize you're given a sack and the maximum weight capacity of the sack is mentioned.
And you have to pick items from the array which is given over here and add them into the knapsack.
And the aim is to maximize the profit in the knapsack.
And the criteria given in the question is that you can take part of an item or a fraction of an item,
and you can add a fraction of an item to the sack.
So that's allowed.
So this is the fractional knapsack problem.
And in the next video let's get started.
And let's try to think about the approach that we can take to solve this question.