Fractional Knapsack Problem

Statement:

A thief has a bag or knapsack that can contain maximum weight W of his loot. There are n items and the weight of 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.

Algorithm:

Take as much of the item with the highest value per weight (vi/wi) as you can. If the item is finished then move on to next item that has highest (vi/wi), continue this until the knapsack is full. v[1 … n] and w[1 … n] contain the values and weights respectively of the n objects sorted in non increasing ordered of v[i]/w[i] . W is the capacity of the knapsack, x[1 … n] is the solution vector that includes fractional amount of items and n is the number of items.

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];
}

Analysis:

We can see that the above algorithm just contain a single loop i.e. no nested loops the running time for above algorithm is O(n). However our requirement is that v[1 … n] and w[1 … n] are sorted, so we can use sorting method to sort it in O(nlogn) time such that the complexity of the algorithm above including sorting becomes O(nlogn).