Fractional Knapsack Problem

Problem Statement

Given a set of N items each having value V with weight W and the total capacity of a knapsack. The task is to find the maximal value of fractions of items that can fit into the knapsack.

Examples:
Input: A[] = {{60, 20} , {100, 50}, {120, 30}}, Total_capacity  = 50
Output: 180.00
Explanation: Take the first item and the third item. Total value = 60 + 120 = 180 with a total capacity of 20 + 30 = 50

Input: A[] = {{500, 30}}, Total_capacity = 10
Output: 166.67
Explanation: Since the total capacity of the knapsack is 10, consider one-third of the item.

Brute Force Approach

The most basic approach is to try all possible subsets and possible fractions of the given set and find the maximum value among all such fractions.

The time complexity will be exponential, as you need to find all possible combinations of the given set.

Efficient Approach(Greedy)

The Fractional Knapsack problem can be solved efficiently using the greedy algorithm, where you need to sort the items according to their value/weight ratio.

Algorithm 

• Sort the given array of items according to weight / value(W /V) ratio in descending order.
• Start adding the item with the maximum W / V ratio.
• Add the whole item, if the current weight is less than the capacity, else, add a portion of the item to the knapsack.
• Stop, when all the items have been considered and the total weight becomes equal to the weight of the given knapsack.

C++ Implementation

struct item
{
    int value,weight;
};
bool cmp(item a,item b)
{
    double r1=(double)a.value/a.weight;
    double r2=(double)b.value/b.weight;
    return(r1>r2);
}
double fractionalknapsack(item A[],int Total_Capacity,int n)
{
    sort(A,A + n,cmp);
    int cur_weight = 0;
    double final_val = 0.0;
    for(int i=0;i<n;i++)
    {
        if(cur_weight + arr[i].weight <= Total_Capacity)
        {
            Cur_weight += A[i].weight;
            Final_val += A[i].value;
        }
        else
        {
            int remain = Total_capacity - cur_weight;
            Final_val += A[i].value * ((double)remain / A[i].weight);
        }
    }
    return final_val;
}

JavaImplementation

fractionalknapsack(int[] val,int[] weights, int tot_capacity)                               {
        Items[] iVal = new Items[weight.length];
  
        for (int i = 0; i < wt.length; i++) {
            iVal[i] = new Item(weight[i], value[i], i);
        }
  
        Arrays.sort(iVal, new Comparator<ItemValue>() {
            @Override
            public int compare(Items o1, Items o2)
            {
                return o2.cost.compareTo(o1.cost);
            }
        });
  
        double totalValue = 0d;
  
        for (Items i : iVal) {
  
            int curWt = (int)i.weight;
            int curVal = (int)i.value;
  
            if (capacity - curWt >= 0) {
                capacity = capacity - curWt;
                totalValue += curVal;
            }
            else {
               double fraction = ((double)capacity / (double)curWt);
                totalValue += (curVal * fraction);

               capacity
                    = (int)(capacity - (curWt * fraction));
                break;
            }
        }
  
        return totalValue;
    }
  
    static class Items {
        double cost;
        double weight, value, ind;
  
        public ItemValue(int weight, int value, int ind)
        {
            this.wt = wt;
            this.val = val;
            this.ind = ind;
            cost = new Double((double)value / (double)weight);
        }
    }

PythonImplementation

def fractionalknapsack(values,weights,Total_capacity):
    n = len(values)

    def score(i) : return values[i]/weights[i]

    items = sorted(range(n)  , key=score , reverse = True)
    sel, value,weight = [],0,0
    for i in items:
        if weight +weights[i] <= capacity:
            sel += [i]
            weight += weights[i]
            value += values [i]
    return value

Time Complexity: O(N *log N) where N is the size of the array.
Space Complexity: O(1) because no extra space is needed.

Practice Question

0-1 Knapsack

Frequently Asked Questions

How do you solve fractional knapsack?
Fractional knapsack can be solved using greedy algorithms.

What is the time complexity of fractional knapsack problems?
The time complexity of the fractional knapsack problem is O(NlogN).

Can we solve fractional knapsack using dynamic programming?
Yes, fractional knapsack can be solved using dynamic programming, but it will not be efficient as it will take memory.

Which approach is the best in knapsack problems?
For 0/1 knapsack, the dynamic programming approach is the best, while for fractional knapsack, the greedy approach is optimal.