Greedy Algorithm Knapsack Problem Policy 1 Choose the lighte

Greedy Algorithm

Knapsack Problem

Policy 1: Choose the lightest remaining item, and take as much of it as can fit.

Policy 2: Choose the most profitable remaining item, and take as much of it as can fit.

Prove by a counter example that Policy 1 does not guarantee an optimal solution. Same with Policy 2.

Solution

An optimal solution would be where a user collect an items which maximise his profit for a given capacity of valuables which he can taken out.

So Lets take an example where,
item:           1       2       3
Price(P):       30$       20$       10$
Weight(W):       5       3       3
(P/W):           6       6.66   3.33

Lets say Capacity (C)= 7

Now Lets consider Policy1, which says Choose the lightest remaining item, and take as much of it as can fit:

In our case, initially lightest item is item2 having weight 3.
then after lightest remaining item is item3, having weight 3.
So total weight(item2+item3)= 3 + 3 = 6
Since Capacity is 7 so 1 unit more weight we can take from remaining item1.
Total weight(item2+item3+item1) = 3 + 3 + 1 = 7

Total profit gain = (6.66x3) + (3.33x3) + (6x1) = 20 + 10 + 6 = 36$

Now Lets consider Policy2, which says Choose the most profitable remaining item, and take as much of it as can fit:
In our case most profitable item is item1 whose price is 30.
then after item 2 whose price is 20.
But we will take only two units from item2 as we have capacity of 7 only.
So total weight we have(item1 + item2) = 5 + 2 = 7

Total profit gain = (6x5) + (6.66x2) = 30 + 13.32 = 43.32$

Both of these solutions are not optimal because we can only have an optimal solution when we choose the items which are having highest price per unit weight.
So Optimal solution would be as:
First choose item2 which is having price per unit = 6.66 and then choose remaining weight till capacity from item1.
So total weight(item2+item1)= 3 + 4 = 7

Total profit gain = (6.66x3) + (6x4) = 20 +24 = 44$

Hence we prooved that policy1 and policy2 does not give us an optimal solution. We can only achive an optimal solution by choosing an items having highest price per unit weight.