Fractional Knapsack

Greedy approach is to try all possible combinations in a sequence to find a optimal solution.

You can imagine the knapsack problem like

"a thief having a bag which can hold up to a certain weight W. He found some N items in a house with each having some value V and weight W. So in order to gain maximum value by accumulating items up to the maximum weight he can carry in his bag, he should identify which item should be taken in which quantity"

Here he can go for a greedy approach by trying all possible sequences. we say this as fractional knapsack because any item can be taken in fractional quantity instead of taking as a whole.

The below example shows how such problems can be solved.

consider maximum weight  of the sack is w=15. There are 5 items (n=5). The weights of the 5 items are 12,1,2,1,4 respectively. Their values are 4,2,2,1,10 respectively. The maximum profit that can be obtained is?

Answer : The idea is to calculate the profit/weight value for each item

Item	1	2	3	4	5
Weight	12	1	2	1	4
Value (profit)	4	2	2	1	10
Profit/weight	0.3	2	1	1	2.5

Now sort according to the profit/weight values in descending order.

this gives

Item	5	2	3	4	1
weight	4	1	2	1	12
P/w	2.5	2	1	1	0.3

This tell us we will get maximum profit if we add items to the sack in the above order until we reach the maximum weight

So now we take each item in the above sorted order until the weight is 15(Maximum)

This goes like this

                    item 5 + item 2 + item 3 + item 4 

weight ->      4       +    1     +    2     +    1     = 8

still we can accumulate a weight of 15-8 = 7. so from last item in the list i.e item 1 we cannot add the whole item as it weighs 12. so,we will take a fraction that weighs 7.

item 1 actual weight is 12. we take 0.58 fractional part of item 1 that weights as 7

so the profit we get will be 0.58 * 4 

  

Therefore, the total profit we get is

10+2+2+1+0.58*4 = 17.32

The maximum profit that can be achieved is 17.32.

To sum up, the idea here is to find the profit by wight ratio that helps in finding how much profit we will get for that weight. so we will add a unit quantity of items until we reach maximum weight or nearer to maximum weight, so that the last item we add will be taken in fraction upto which we can accommodate in the bag.

Dont be wondered after seeing a book dedicated for knapsack solutions. You can find it here