Fractional Knapsack Problem | DAA

Fractional Knapsack Problem

A thief has a bag or knapsack that can contain the maximum weight W of his loot. There are n items and the weight of an ith item is wi and it worth vi. Any amount of item can be put into the bag i.e. xi fraction of item can be collected, where 0<=xi<=1. Here the objective is to collect the items that maximize the total profit earned.

Here we arrange the items by ratio vi/wi.

Algorithm

GreedyFracKnapsack(W, n)

{

    for (i = 1; i <= n; i++)

    {

        x[i] = 0.0;

    }

    tempW = W;

    for (i = 1; i <= n; i++)

    {

        if (w[i] > tempW)

            then break;

        x[i] = 1.0;

        tempW -= w[i];

    }

    if (i <= n)

        x[i] = tempW / w[i];

}

We can see that the above algorithm just contains a single loop i.e. no nested loops the running time

for the above algorithm is O(n). However our requirement is that v[1 ... n] and w[1 ... n] are sorted,

so we can use the sorting method to sort it in O(n log n) time such that the complexity of the algorithm above including sorting becomes O(n log n).

Example: Consider five items along with their respective weights and values,

I = {I1, I2, I3, I4, I5}

w = {5, 10, 20, 30, 40}

v = {30, 20, 100, 90, 160}

The knapsack has a capacity of W=60, then find optimal profit earned by using a fractional knapsack.

Solution:

Step 1: Initially

Items	Wi	Vi
I1	5	30
I2	10	20
I3	20	100
I4	30	90
I5	40	160

Step 2: Calculate vi/wi as,

Items	Wi	Vi	Pi=vi/wi
I1	5	30	6.0
I2	10	20	2.0
I3	20	100	5.0
I4	30	90	3.0
I5	40	160	4.0

Step 3: Arranging the items with decreasing order of Pi as,

Items	Wi	Vi	Pi=vi/wi
I1	5	30	6.0
I3	20	100	5.0
I5	40	160	4.0
I4	30	90	3.0
I2	10	20	2.0

Now filling the knapsack according to decreasing value of Pi

Maximum value= v1+v2+new(v3) = 30+100+140=270