Welcome back.
Let's now implement the code for the approach that we have discussed in the previous video.
Okay.
So we're given this function over here fractional knapsack.
And we are given the weight capacity of the knapsack.
And we are also given this array over here.
And it's mentioned in the question that every element in this array will be an array by itself, which
will have two elements of which the first represents the profit and the second represents the weight
of that particular item.
Okay.
And we are also given n, which is the number of elements or the size of this array over here.
Now to start with we are going to sort this array over here by the ratio of profit by weight of every
element in this array.
And we are going to do it in descending order.
So let's go ahead and do that.
So I can say r dot sort.
And I have a comma B over here.
And the criteria is that we're going to sorted in descending order by the ratio of profit by weight
okay.
So let's implement that.
So I have b at zero divided by b at one minus a at zero divided by a at one okay.
And again remember in the question is given that every element in this array will have this structure
where the first element is the profit and the second element is the weight.
Okay.
So b at zero would give the profit, B at one would give the weight.
Similarly, a at zero would represent profit and a at one represents weight.
So we are sorting the array in descending order by the profit by weight ratio.
So that's what we're doing over here.
And after this let's say remaining weight is equal to W because as of now nothing has been added to
the knapsack.
And because nothing has been added to the knapsack, the value in the knapsack is also zero.
Now what we will do is we will just go through each element in the array, okay?
And because we have already sorted the array by the profit by weight ratio in descending order, we
would just need to take the element that we are getting.
So we start at index zero and go up to index n minus one.
And we keep adding as much as possible of every item.
Okay.
And before we decide whether we can add a particular element or sum of a particular element to the knapsack,
we have to check if the remaining weight at that particular instance is equal to zero, because if that
is the case, then we will not be able to add more items, and we would just have to break out of this
for loop.
But if that is not the case, then we first have to decide the weight of this particular item that can
be added to the knapsack.
And that would be math dot min, or the minimum between the remaining weight and the weight of this
particular item which is given to us.
Okay, that would be our at I at one.
Again, let me quickly explain this.
Now let's say the remaining weight that can be added is two units.
And let's say for a particular item we are given just one unit okay.
So the weight is just one.
So in that case, even though the remaining weight that can be added to the knapsack is two, because
we don't have two units of this particular item, we would just be able to add only one.
But on the other hand, if this over here would be three.
Okay.
Now, because the remaining weight that can be added is just two units.
So that's why we will not be able to add three units, but rather only two units to the knapsack.
So that's why the weight that can be added to the knapsack at this point would be the minimum between
the remaining weight and the weight of the given item.
Okay.
And after we have decided the weight of the item that's going to be added to the knapsack, we are going
to reduce the remaining weight by that amount.
Okay.
So we can say remaining weight minus is equal to weight.
And all that now remains is to increment the value in the knapsack by the value of the item that we
have added to the knapsack, okay.
And therefore value is going to be value plus the value of the item that has been added to the knapsack.
And to find the value of that, we would just have to take the value of the total item which is given
to us, and then divide it by the weight of that particular item which we have.
So this would be the value of one unit of this particular item.
And then we would just have to multiply it with the number of units of weight of this particular item
that we have added to the knapsack.
Okay.
So that would be this.
Again quickly explaining this like if we know that, for example, five units of mangoes okay, five
units of weight, it can be kilograms or anything costs let's say $10.
Now, if we were only able to add two units of weight to the knapsack, in that case the increment in
the value would be this ten over here divided by five into two.
Okay.
And that's what we are doing over here.
And once we are out of this for loop and we would come out of this for loop either when remaining weight
becomes equal to zero, or if we have gone through all the given items, and then all that remains is
to return the value.
Okay.
And that's it.
Now let's go ahead and run this code and see if it's passing all the test cases okay.
So there's an error I have named this wrongly decimal remaining weight.
Right.
So this w has to be caps.
So let's correct that.
Now let's go ahead and run this code and see if it's working.
And you can see that it's passing all the test cases.
So this is how we can solve the fractional knapsack problem.
And notice that we have used a greedy algorithm to solve this question.