The fractional knapsack problem

The fractional knapsack problem is a greedy-based problem and also an extension of the classic 0-1 knapsack problem. You can read about the 0-1 knapsack problem here.

Problem Description

Given n items having certain value and weight, put these items in a knapsack with given maximum capacity (maxWeight). The goal here is to find possible maximum total value in the knapsack. Here fraction of items can be used i.e we can break an item. For example :

Input:
n=3
maxWeight=50
weights={10,20,30}
value={50,40,90}

Output:
160.00

In the above example, we can fully select item 0 and item 2. This will give total value = 50+90 = 140 with total weight = 10+30 = 40. For remaining weight space of 50-40=10, we can use (1/2)th of item 1 which will have weight = 20/2 = 10 and value 40/2=20. So total value will be 50+90+20 = 160 and total weight will be 10+30+10=50 i.e. <=maxWeight. This is the possible maximum answer.

Observation

Here the key observation is that we need to use items fully until we lack weight space for the particular item. In that scenario, we can break the item to fill the left weight space.

Greedy approach

As we can break the item into any fraction and use it, we need to normalize it. Suppose we have an item of weight = a and value = b, we can break that item into 'a' number of items each of value (b/a). For eg. if we have an item of weight = 30 and value = 120, we can break that item into 30 items, each having value (120/30)=4 i.e. we have 30 items having weight = 1 and value = 4.

To maximize the total value inside the knapsack, we will sort the items with reference to (value/weight) ratio using the custom compare function in Sort(). One by one we will check for an item and as per the left weight space out of maxWeight inside the knapsack, we will use the current weight.

Case 1: If our current item is having a weight less than or equal to the left weight space inside the knapsack, we didn't need to break the item as the whole item can be accommodated inside, so we will add that item fully. If we have an item of weight 10 and the left weight space in the knapsack is 20 then we can use that item fully without breaking it.

Case 2: If our current item is having a weight more than the left weight space inside the knapsack, we will break the item and use only the fraction that is required. For eg., if we have the capacity(max weight) of knapsack = 10 and the current total weight of knapsack = 8. Current item is having weight = 30 and value = 120. In order to fill 10-8 = 2 weight space in knapsack we will use only (1/15)th of item i.e weight = (30/15) = 2 having value (120/30)*2 = 8.

struct Item{
    int weight,value;

};

class greedy_approach{

    static bool compare(Item a,Item b){
        return (double)a.value/a.weight>(double)b.value/b.weight;
    }

    public:
    double fractional_knapsack(int maxWeight,int n,Item weights[]){
        sort(weights,weights+n,compare);
        double ans = 0 ;
        for(int i=0;i<n;i++){
            if(maxWeight>=weights[i].weight){
                maxWeight-=weights[i].weight;
                ans+=weights[i].value;
            }else{
                ans+=maxWeight*(double)weights[i].value/weights[i].weight;
                break;
            }
        }
        return ans;
    }
};

Here we use Item struct to reduce code complexity and can avoid making extra vectors and maps to store weights and values.

Time Complexity : O(n*logn). We use Sort() and an O(n) loop. The sort takes approx. n*logn time.
Space Complexity : O(n).