In the previous video, we have discussed the approach that we can take to solve this question.
Let's now go ahead and write the pseudocode for the approach that we came up with.
Now again, let's take the example where the capacity of the knapsack is 45.
And this is the array which is given to us where each item is an array by itself.
And the first item over here represents the profit that this item can give.
If ten kilograms of this item were added to the knapsack.
And we have seen that for solving this question, we would need to calculate the profit by weight ratio.
So let's go ahead and calculate that and note it down over here.
And to solve this question we would need a function.
Let's just call it fract for fractional knapsack.
And to this function we would pass the weight which is 45.
In this case the array which is this array over here.
And let's say we are also passing in to the function over here which indicates how many items are given
to us.
And in this case we are given five items.
Now in the body of the function, the first thing that we would have to do is we would have to sort
this array, which is given to us on the basis of the profit by weight ratio in reverse order, so that
the first item in the array becomes the item with the highest profit by weight ratio.
Okay.
So let's go ahead and note that down over here.
So we will sort the array which is given to us on the basis of the profit by weight ratio in reverse
order.
Now once we have done that we will set the remaining capacity that can be added to the knapsack to equal
w, because at this point nothing has been added to the knapsack, and the profit or the value in the
knapsack will be set to zero again, because for the same reason that nothing has been added to the
knapsack so far.
All right.
And then we would have to write some code or do some operations over here to identify the maximum value
that can be added to the knapsack.
And ultimately we would just return the value.
Okay.
So this is the skeleton.
Now let's go ahead and fill this part of the pseudocode.
So what we would do is we would go through each item in the array.
And remember at this point array has been sorted in the reverse order on the basis of the profit by
weight ratio.
So the first item that we get would have the highest profit by weight ratio.
The second item in array at this point has the second highest profit by weight ratio.
And it goes on in this manner.
So at this point we would just iterate over each item in the array.
And then we will check whether the remaining capacity is not zero.
Because if it's zero, then nothing more can be added to the knapsack and we can just break out of the
for loop.
Okay.
So if the remaining capacity is equal to zero, we'll just break out of the for loop or we'll just get
out of it.
But if it is not equal to zero, then we will have to decide how much of the particular item at hand
can be included into the knapsack.
Now again, there are two things to keep in mind with this regard.
The first thing is how much is the remaining capacity that can be added to the knapsack?
And the second is how much of the item at hand is given to us, like over here.
For example, for this item, we just can add ten kilograms of that item to the knapsack because that's
all that we have.
Even if the remaining capacity is 40, we cannot add 40kg of this item.
We can just add ten.
So to identify the capacity of the item at hand that can be added to the knapsack, we have to identify
the minimum between the remaining capacity that can be added to the knapsack and the item weight which
is given to us in the array.
Okay, so the minimum between these two would be the capacity that we can take of this particular item
and add to the knapsack.
Okay.
And when we do that the value in the knapsack would increase okay.
But by how much would it increase.
The amount by which the value would increase is the product of the capacity that we did add.
Multiplied with the per unit value.
Okay, again, this is pretty straightforward.
If one unit of something costs, let's say $10, then five units of that item would cost five into $10.
Right.
So in a similar manner, we would just need to multiply the capacity that we have decided to include
into the knapsack for that particular item with the per unit value of that item.
For example, if we take this item over here, we know that the per unit value is seven.
And hypothetically let's say we're just taking five units.
If that were the case, then the value that would be increased in the knapsack or the profit that would
be increased in the knapsack would be seven into five.
And that's what we're doing over here.
Okay.
So we are incrementing the value by the capacity multiplied with the per unit value of that particular
item.
And when this item has been added to the knapsack, there's one more thing that we have to do, which
is to reduce the remaining capacity that can be added to the knapsack by the capacity that has been
added.
So the remaining capacity would equal the remaining capacity minus the capacity that we have added to
the knapsack.
And that's it.
So in this way, once we get out of the for loop, we would have added the items to the knapsack in
a manner that would maximize the value in the knapsack.
And then we would just need to return the value.
So this is the pseudocode for the approach that we've discussed in the previous video.
Now in the next video let's go ahead and take a look at the complexity analysis for this approach.