Fractional Knapsack Problem

The Knapsack problem is a class of optimization problems in which we have to find the maximal answer among all the various possibilities given in the question. There are three types of knapsack problems $i.e.$ 0-1 Knapsack, Fractional Knapsack, and Unbounded Knapsack. In this article, we will be seeing the fractional knapsack Problem in detail.

Scope

• This article defines the fractional knapsack problem in detail with the help of examples.
• Both, the brute force and the efficient approach for solving the fractional knapsack problem have been described in detail.
• The efficient algorithm has been implemented in Java, C++, Python, and C#.

Introduction to Fractional Knapsack Problem

Given two arrays named value and weight of size $n$ each, where value[i] represents the value and weight[i] represents the weight associated with the $i^{th}$ item. Also, we have been provided a knapsack with a maximum capacity of W.

The task is to pick some items (possibly all of them) such that the sum of values of all the items is maximized and the sum of weights of all the items is at most W.

As the name Fractional suggests, here we are allowed to take a fraction of an item. For example, if the weight of an $i^{th}$ item is $x$ units, then we can have the following choices :

1. Do not take any fraction of the $i^{th}$ item.
2. Take the item as a whole.
3. Take any integer weight of the $i^{th}$ item $i.e.$ For an item of weight $20$ Kg. we can either take $1$ Kg, $2$ Kg, …, or $19$ Kg but we are not allowed to take $1.2$ Kg or $5.7$ Kg.

Note that if we are taking a fraction of an item, we get the value in the same fraction.

Example

Input :

weight[] = {10, 30, 20, 50}
value[] = {40, 30, 80, 70}
W = 60

Output :

162

Explanation :
Let’s say we take the $1^{st}$ item as a whole, so we obtain a value of40and the capacity of the knapsack is now reduced to50. Then we pick the $3^{rd}$ item as a whole, after which we obtain a value of120and the capacity of the knapsack is now reduced to30.

Now we take 30 Kg. of the $4^{th}$ item, which will add $\frac{70}{50} \times 30 = 42$ to our value due to which we obtained a value of 162 and we are left with no space in the knapsack hence we can conclude the result to be 162.

It can be proved that there is no other choice of picking item(s) such that the value of the chosen item(s) exceeds 162.

Techniques to Solve the Fractional Knapsack Problem

Brute Force Approach

Since for an item of weight $x$, we have $x+1$ choices $i.e.$ taking 0 Kg. of the item, taking 1 Kg. of the item, taking 2 Kg. of the item, …., taking $x$ Kg. of the item. Therefore, with the brute force approach, we can check the value of all the possibilities from the set of items provided.

Example :

Let’s say we have the following items :

And a knapsack with a capacity of 3.

So, as per the brute force algorithm, we can have the following choices :
In the below-given matrix, the value in the $\text{cell}_{i, j}$ denotes the amount of weight of $j^{th}$ item we are taking in the $i^{th}$ choice.

The highest possible value we can obtain is 14 $i.e.$ by picking the 1 Kg. of all the items.

Greedy Approach

We have seen that the brute force approach works every time but on a reasonable large input, it will take a very huge amount of time to calculate the answer.

So, we can opt for a greedy algorithm. We can have several potentially correct strategies, some of the obvious ones are :

1. Picking the items with the largest values first.
2. Picking the items with the lowest weights first.
3. Picking the items based on some sort of ratio among their values and weights.

In the next section of this article, we will see which of the above approach is correct and the reason behind their correctness.

Example of Solving a Fractional Knapsack Problem Using Three Approaches

Let’s say we have the following input :

Items :

Capacity (W) : 70

Approach – 1 : Picking Items with the Largest Value

Using the approach we can obtain a value of $80+70=150$

Approach – 2 : Picking Items with the Smallest Weight

Using the approach we can obtain a value of $80+40+50+13.33=183.33$

Approach – 3 : Picking Items Based on Ratio

As per this approach, we will find the value obtained per unit weight for all items. And we will take the items with the largest value per unit weight first.
So we will have our input modified to :

Now picking items as follows :

Using the approach we can obtain a value of $80+40+50+28=198$

We can see that by following the third approach we can obtain the maximum value. This is because in other approaches we were giving importance to only one parameter but in the third approach, we considered the ratio of both to obtain the maximal value.

Also, another possible way is to find the ratio of Weight Gained Per unit value (which is reciprocal of the current ratio), and then choose items in ascending order of the ratio’s value.

Greedy Algorithm

As seen in the previous section, for each item we will calculate the ratio of value to its weight $i.e. \frac{value_i}{weight_i}$ which denotes the value obtained per unit weight.

Now to get the maximal value, we will sort the items in the descending order of the ratio so that items with greater ratio values are picked before items with a comparatively smaller ratio.

While picking an item, we will check if it is possible to take it as a whole or not because we are constrained by the capacity of the knapsack. So, if it is not possible to pick the item as a whole, we will pick as much weight of the item as we can.

The algorithm is as follows :

• Sort the items in descending order using a custom comparator based on the value per unit weight ratio.
• Declare a variable of floating-point type, ans, and initialize it with 0.
• Iterate from $i = 0$ To $i =$ Item.length $- 1$ and do the following :
• If it is possible to take the item[i] as a whole do the following :
  • Add value[i] to the ans, because we have picked this item as a whole.
  • Subtract weight[i] from the Capacity, because picking this item will reduce the capacity.
• Otherwise do the following :
  • Let’s say you are left with capacity $y$.
  • Add $\frac{value[i]}{weight[i]} \times y$ to ans.
  • Subtract $y$ from Capacity.
  • Terminate the loop as the Knapsack is full.
• Return the result $i.e.$ ans.

Pseudocode

// Function to find the maximum
// value that can be obtained.
function getMax (weight, value,  capacity):

    // Finding the size of the array.
    n = weight.length

    // Sorting the weight and value
    // array  in the decreasing order
    // of the value per unit weight ratio.
    Sort(weight, value, value[i]/weight[i])

    // Initializing answer with 0.
    ans = 0

    // Iterating over the arrays
    For i = 0 To i = n - 1:
        wt = weight[i]
        val = value[i]

        valuePerUnitWeight = value[i]/weight[i]

        // If we can take the whole item.
        If (capacity >= wt):
            // Adding value of current item.
            ans = ans + val

            // Reducing capacity by wt.
            capacity = capacity - wt

        // Otherwise we can take a fraction.
        Else:
            // Adding the value of the part that we can take.
            ans = ans + valuePerUnitWeight * capacity

            // Now we are left with no space so
            // we will terminate the loop.
            capacity = 0
            break

    // Returning the answer
    return ans
end function

Java Implementation

import java.util.*;

public class Main {

  // Class to define an item.
  static class Item {
    // Weight and Value of
    // an Item.
    int weight, value;
    // Value one can obtain by
    // taking a unit weight (1 Kg).
    double valuePerUnitWeight;

    // Constructor
    Item(int weight, int value) {
      this.weight = weight;
      this.value = value;

      // Calculating the ratio.
      valuePerUnitWeight = (double) (value) / (weight);
    }
  }

  // Function to find the maximum
  // value that can be obtained.
  static double getMax(int weight[], int value[], int capacity) {
    // Finding the size of the array.
    int n = weight.length;

    // Making a new List array (say list)
    // of item type.
    List<Item> list = new ArrayList<>();

    // Filling elements in the list.
    for (int i = 0; i < n; i++) {
      list.add(new Item(weight[i], value[i]));
    }

    // Sorting the list in the decreasing
    // order of the value per unit weight ratio.
    Collections.sort(
      list,
      new Comparator<Item>() {

        public int compare(Item i1, Item i2) {
          if (i1.valuePerUnitWeight > i2.valuePerUnitWeight) return -1;
          return 1;
        }
      }
    );

    // Initializing answer with 0.
    double ans = 0;

    // Iterating over the list
    for (int i = 0; i < n; i++) {
      int wt = list.get(i).weight;
      int val = list.get(i).value;
      double valuePerUnitWeight = list.get(i).valuePerUnitWeight;
      // If we can take the whole item.
      if (capacity >= wt) {
        // Adding value of current item.
        ans += val;

        // Reducing capacity by wt.
        capacity -= wt;
      }
      // Otherwise we can take a fraction.
      else {
        // Adding the value of the part that we can take.
        ans += valuePerUnitWeight * capacity;

        // Now we are left with no space so
        // we will terminate the loop.
        capacity = 0;
        break;
      }
    }
    // Returning the answer
    return ans;
  }

  public static void main(String args[]) {
    // Defining the weights and values
    // of the item.
    int weight[] = { 10, 30, 20, 50 };
    int value[] = { 40, 30, 80, 70 };
    int capacity = 60;

    System.out.println(
      "Maximum value that" +
      " can be obtained is " +
      getMax(weight, value, capacity)
    );
  }
}

Output :

The maximum value that can be obtained is 162.0

C++ Implementation

#include<bits/stdc++.h>
using namespace std;


// Class to define an item.
class Item{
public:
    // Weight and Value of
    // an Item.
    int weight, value;
    // Value one can obtain by
    // taking a unit weight (1 Kg).
    double valuePerUnitWeight;

    // Constructor
    Item (int Weight, int Value){
        weight = Weight;
        value = Value;

        // Calculating the ratio.
        valuePerUnitWeight = (double)(Value)/(Weight);
    }
};

// Comparator used in sorting
bool myComparator(const Item &i1, const Item &i2){
    return i1.valuePerUnitWeight > i2.valuePerUnitWeight;
}

// Function to find the maximum
// value that can be obtained.
double getMax (int weight[], int value[],
                int capacity, int n){

    // Making a new List array (say list)
    // of item type.
    vector<Item> list;

    // Filling elements in the list.
    for (int i = 0; i < n;i++){
        list.push_back(Item(weight[i], value[i]));
    }

    // Sorting the list in the decreasing
    // order of the value per unit weight ratio.
    sort(list.begin(), list.end(), &myComparator);
    // Initializing answer with 0.
    double ans = 0;

    // Iterating over the list
    for(int i = 0; i < n; i++){
        int wt = list[i].weight;
        int val = list[i].value;

        double valuePerUnitWeight =
                    list[i].valuePerUnitWeight;
        // If we can take the whole item.
        if (capacity >= wt){
            // Adding value of current item.
            ans += val;

            // Reducing capacity by wt.
            capacity -=  wt;
        }
        // Otherwise we can take a fraction.
        else{
            // Adding the value of the part that we can take.
            ans += valuePerUnitWeight * capacity;

            // Now we are left with no space so
            // we will terminate the loop.
            capacity = 0;
            break;
        }
    }
    // Returning the answer
    return ans;
}
int main(){

    // Defining the weights and values
    // of the item.
    int weight[] = {10, 30, 20, 50};
    int value[] = {40, 30, 80, 70};
    int capacity = 60;

    cout << "Maximum value that " <<
        "can be obtained is " <<
            getMax(weight, value, capacity, 4) << endl;
}

Output :

The maximum value that can be obtained is 162.0

Python Implementation

# Class to define an item.
class Item:
    # Constructor
    def __init__(self, Weight, Value):
        # Weight and Value of
        # an Item.

        self.weight = Weight
        self.value = Value

        # Value one can obtain by
        # taking a unit weight (1 Kg).
        self.valuePerUnitWeight = (Value)*1.00/(Weight)

    # Comparator to sort
    def __lt__(self, other):
        return self.valuePerUnitWeight > other.valuePerUnitWeight

# Function to find the maximum
# value that can be obtained.
def getMax (weight, value,  capacity):

    # Finding the size of the array.
    n = len(weight)

    # Making a new List array (say list)
    # of item type.
    list = []

    # Filling elements in the list.
    for i in range(n):
        list.append(Item(weight[i], value[i]))


    # Sorting the list in the decreasing
    # order of the value per unit weight ratio.
    list.sort()

    # Initializing answer with 0.
    ans = 0

    # Iterating over the list
    for i in range(n):
        wt = list[i].weight
        val = list[i].value

        valuePerUnitWeight = list[i].valuePerUnitWeight
        # If we can take the whole item.
        if (capacity >= wt):
            # Adding value to the current item.
            ans = ans + val

            # Reducing capacity by wt.
            capacity = capacity - wt

        # Otherwise we can take a fraction.
        else:
            # Adding the value of the part that we can take.
            ans = ans + valuePerUnitWeight * capacity

            # Now we are left with no space so
            # we will terminate the loop.
            capacity = 0
            break

    # Returning the answer
    return ans

 # Driver code

# Defining the weights and values
# of the item.
weight = [10, 30, 20, 50]
value = [40, 30, 80, 70]
capacity = 60

print("Maximum value that can be obtained is", getMax(weight, value, capacity))

Output :

The maximum value that can be obtained is 162.0

C# Implementation

using System;
using System.Collections;

class main{
    // Class to define an item.
    class Item{
        // Weight and Value of
        // an Item.
        public int weight, value;
        // Value one can obtain by
        // taking a unit weight (1 Kg).
        public double valuePerUnitWeight;

        // Constructor
        public Item (int weight, int value){
            this.weight = weight;
            this.value = value;

            // Calculating the ratio.
            valuePerUnitWeight = (double)(value)/(weight);
        }
    }
    // Comparator to sort Item array
    class myComparator : IComparer{
        public int Compare(Object ob1, Object ob2){
            Item i1 = (Item)(ob1);
            Item i2 = (Item)(ob2);

            if(i1.valuePerUnitWeight < i2.valuePerUnitWeight)
                return 1;
            return -1;
        }
    }
    // Function to find the maximum
    // value that can be obtained.
    static double getMax (int[] weight,
                    int[] value, int capacity){

        // Finding the size of the array.
        int n = weight.Length;

        // Making a new List array (say list)
        // of item type.
        Item[] list=new Item[n];

        // Filling elements in the list.
        for (int i = 0; i < n; i++){
            list[i]= new Item(weight[i], value[i]);
        }

        // Sorting the list in the decreasing
        // order of the value per unit weight ratio.
        Array.Sort(list, new myComparator());

        // Initializing answer with 0.
        double ans = 0;

        // Iterating over the list
        for(int i = 0; i < n; i++){
            int wt = list[i].weight;
            int val = list[i].value;
            double valuePerUnitWeight =
                        list[i].valuePerUnitWeight;
            // If we can take the whole item.
            if (capacity >= wt){
                // Adding value of current item.
                ans += val;

                // Reducing capacity by wt.
                capacity -=  wt;
            }
            // Otherwise we can take a fraction.
            else{
                // Adding the value of the part that we can take.
                ans += valuePerUnitWeight * capacity;

                // Now we are left with no space so
                // we will terminate the loop.
                capacity = 0;
                break;
            }
        }
        // Returning the answer
        return ans;
    }
    static void Main(string[] args){

        // Defining the weights and values
        // of the item.
        int[] weight = {10, 30, 20, 50};
        int[] value = {40, 30, 80, 70};
        int capacity = 60;

        Console.WriteLine("Maximum value that" +
                "can be obtained is " + getMax(weight, value, capacity));
    }
}

Output :

The maximum value that can be obtained is 162.0

Complexity Analysis

• Time Complexity :
• Sorting the item set will require at least $O(n \log{n})$ time, and Iterating over the sorted item set will require $O(n)$ time. Hence the overall time complexity is $O(n\log{n} + n) \simeq O(n\log{n})$
• Space Complexity :
  Doesn’t matter which sorting algorithm we use for sorting, it will require $O(n)$ extra space because we need to combine value and weight arrays using a 2-D array/list to sort them. Hence the overall space complexity is $O(n)$.

We have seen the time complexity to be $O(n\log{n})$ but in the best case, we can optimize it further to $O(n)$.

• Let’s see how :
• If the capacity of our knapsack is greater than or equal to the sum of the weights of all the items, we do not need to sort items. Instead, we can select all the items available because we have hefty space to accommodate all of them.
• So, in this case, we just need to find the sum of all the values which will require $O(n)$ time.

Conclusion

• In the fractional knapsack problem, we are allowed to split the items in fractions, unlike the 0-1 Knapsack problem where it is prohibited to split the items.
• Checking for all the possible choices of picking items works well but requires a huge amount of time.
• The Greedy approach uses the value per unit weight ratio of items to select the best choices.