Welcome back.
Let's now think about the approach that we can take to solve this question.
And for discussing that, let's take this example where this is the array which is given to us.
And the capacity of the knapsack is 45.
Okay.
So again remember the question mentions that each item in the array is an array by itself which has
two elements.
And the first element over here represents the profit of that particular item, and the second element
represents the weight of that particular item.
And you can take any units.
Now if you were to take kilogram, this would imply ten kilograms of this particular item, if added
to the knapsack, would increase the profit in the knapsack by 70 units.
And if we take this as kilograms, then this also would be kilograms, and it would imply that the maximum
weight that can be added to the knapsack is 45kg.
So we have understood the question now also do remember in the question it's mentioned that we can take
fractions of an item.
Okay.
Now what would be some of the approaches that can be taken to solve this question.
Maybe person A would say, let's first add this particular item to the knapsack, because it has the
highest value among all the items over here.
So you have 70 over here, 90 over here, 150 over here, 80 and 100 over here.
So this is the highest profit.
And therefore maybe person A tells that let's add this particular item first to the knapsack.
Now another person, let's say person B may say let's add this particular item to the knapsack because
it has the least weight.
And if I add the item with the least weight into the knapsack first, then probably I can keep adding
more items to the knapsack and in that manner maximize my profit.
So probably this is what person B would advocate.
Okay.
And again notice this has the lowest weight among all of these other weights.
So ten is the lowest value among 1020 3015 and 20.
Now what do you think is any of these two approaches the right approach that we should take.
What do you think?
Now, the truth, for that matter is it's not only profit or weight that determines which item gives
us the maximum benefit when we add that particular item to the knapsack, but rather it's the profit
by weight ratio.
Okay.
Because again, you have a knapsack with a fixed capacity.
And therefore what we want is for every unit of capacity or weight that gets increased in the knapsack
by adding something to the knapsack, we want the maximum profit.
Okay.
So for per unit weight we want the highest profit.
And to identify the item that would enable this, we would have to take the profit by weight ratio.
And then whichever item among the items over here has the highest profit by weight ratio, that would
be the item that we would have to first add to the knapsack.
And if possible, we would just fill the knapsack with that particular item.
Okay.
So let's go ahead and see how that works out.
And for that let me make some space over here.
So again, what we have so far discussed is that we are going to make choices.
And again, the solution or filling the knapsack is going to be a step by step process.
And at every step we are going to make a greedy choice.
Or we are going to pick the item that has the highest profit by weight ratio.
So notice how the problem can be solved using a greedy algorithm, because it is satisfying the greedy
choice property and it's satisfying the optimal substructure property.
Now, when I say that this problem satisfies the greedy choice property, what do I mean with it?
Notice at every point we are making the locally optimal choice by trying to pick the item with the highest
profit by weight ratio and with locally optimal choice.
What do I mean?
We are not trying to optimize anything globally.
I'm just trying to make one choice.
And in that one choice at every step, I'm just choosing the item that has the highest profit by weight
ratio.
So it's the locally optimal choice that I am making, or I'm making the optimal choice at this particular
instance, which gives me the highest value or impact.
Okay.
So again that's the item with the highest profit by weight ratio.
And that's why this question satisfies the greedy choice property.
Because if we keep doing that, we would finally end up using all the capacity of the knapsack.
And we would have filled the maximum possible value into the knapsack.
And that's the global optimal solution which we are trying to achieve.
By making these locally optimal choices.
So this question over here satisfies the greedy choice property.
And it also satisfies the optimal substructure property.
Because the optimal solution to the problem contains the optimal solution to subproblems.
And over here, the subproblems are the various steps that we have to take.
Right?
So when we have to make a choice for the first time, we are actually solving a subproblem.
And when you compare the optimal solution to the problem at hand, which is when we would have filled
the knapsack with the correct items in their correct proportions, such that the profit is maximized
and the constraint is met.
So when we take a look at the globally optimal solution, and when we think of each subproblem where
we have some items may be in the knapsack, and we are tasked to make a choice and add something more
to the knapsack.
So when you take a look at the solution to that particular subproblem, you will find that the solution
to those subproblems are there in the global solution as well.
And therefore this question follows the optimal substructure property as well.
Now, to thoroughly understand what we have discussed so far, let's just quickly dry run how the algorithm
would solve this question.
So we are given a knapsack which has a capacity of 45kg.
And then we are given this array of items.
Now let's go ahead and identify the profit by weight ratio of each of these items.
For the first item the ratio would be 70 divided by ten which is equal to seven.
For the second item, the profit by weight ratio is 90 by 20, which is equal to 4.5.
Similarly, the ratio for the next item is 150 by 30, which is equal to five, and the ratio for the
next item is 80 divided by 15, which is five one by three, and the final ratio is 100 by 20, which
is also equal to five.
Now it's given that the capacity of the knapsack is 45 units.
So the highest profit by weight ratio is for this item over here.
And the maximum amount of this item that we can take is ten kilograms because that's all that we have
okay.
So because this has the highest profit by weight ratio and because ten is less than equal to 45.
So let's go ahead and include ten kilograms of this item into our knapsack.
So when we do that the capacity of the knapsack would reduce to 45 minus ten, which is equal to 35.
So we can add items that way a total of 35kg into the knapsack after having added ten kilograms of item
one.
So we proceed.
And when we take a look at the profit by weight ratio of the remaining items, we can see that this
is the second highest value, or among these, this has the highest value, and the maximum amount of
this particular item that is made available to us is 15kg.
And because 15 is less than or equal to 35, we decide to add 15kg of this particular item to the knapsack.
Now the remaining capacity of the knapsack changes to 35 -15, which is equal to 20.
So again we proceed among these three items.
The items with the highest profit by weight ratio are this item over here and this item over here.
And because they have the same profit by weight ratio, we can take any of these.
Now let's say we are proceeding with this one over here okay.
And because we have 30kg of this item available but the remaining capacity is only 20, we can only
take 20 units or 20kg of this item.
And we add that to our knapsack.
And when we do that, the remaining capacity that can be added to the knapsack becomes 20 -20, which
is equal to zero, which means that at this point our knapsack is completely filled.
Now let's go ahead and compute the value or the profit of items in the knapsack, so that we can return
that.
So we have ten kilograms of this particular item.
And therefore the profit of this item that is there in the knapsack is 70.
Okay.
Because the complete item is there in the knapsack.
And when it comes to this item over here, we have 20kg in the knapsack.
Now if we had 30kg the profit would be 150.
Therefore, the profit of 20kg is equal to 150 into 20 divided by 30 okay.
And this simplifies to five into 20 which is equal to 100.
So the profit in the knapsack on account of the presence of this particular item is equal to five into
20, which is 100.
Now what about this item over here we have 15kg of this item in the knapsack.
And that's the complete amount of this item that we have.
And therefore the profit in the knapsack on account of this item is equal to 80.
So that's 80.
Or you can think of it as five one by three into 15 as well.
And again I'm just showing a calculation over here so that you understand one more way in which you
could write the code.
Now five one by three is the unit profit for this item.
And 15 is the units or the weight that is being added.
So if we multiply five one by three into 15, we will get the profit incremented in the knapsack because
of the presence of this particular item.
Now in this case five one by three into 15 will again give you 80.
So the total profit in the knapsack at this point is 70 plus 100 plus 80, which is equal to 250.
And that would be the answer that we will return.
So this is how we can solve this question.
And notice that we have used a greedy algorithm to solve this, where at every step we are just trying
to pick the item with the highest profit by weight ratio.
And in this way we are able to maximize the profit that we can include in the knapsack.