How to Solve the Fractional Knapsack Problem

Introduction

This article will discuss a variation of the 0/1 Knapsack Problem, treated before in this site. The input is the same: a set of items with a weight w, each with an associate profit p. We have to fill a knapsack of capacity W, with the constraint that the inserted set of items has the maximum profit. The difference with the 0/1 counterpart is that we can consider fractions of an item to fill the bag. This variant is known as the Fractional Knapsack Problem.

Problem Example for the Fractional Knapsack Problem

As in the 0/1 discussion we can arrange the items using a bi-dimensional array like { {w1, p1}, {w2, p2}, …}. Consider the following input for the problem:

• N = 3 items with the following w, p couples:
  • { {10, 5}, {20, 15}, {30, 6} }
• W = 10 as capacity

We can solve The Fractional Knapsack Problem with a typical greedy algorithm. We are sure of obtaining the best result by picking each time the item with the higher ratio p/w between profit and weight and if the item weight exceeds the capacity, arranging a fraction of it. For instance, for the above example, we can include {30, 6} and then a fraction of {10, 5}, calculated as the remaining weight, which is 4, divided by 5, that is 4/5 of the element. So, the maximum profit will be (30 + 4/5*10).

A Solution for the Fractional Knapsack Problem

We can generalize the things explained in the above section with the following steps:

• Order the items from the highest ratio p/w to the lowest.
• Use two variables to store the current result and remaining capacity and initialize them to 0 and W.
• For each item:
  • We update the current result with the profit of the current item if it is less or equal to the remaining capacity.
  • Otherwise, we add a fraction of the item defined as (remaining capacity)/(item capacity) and update the current result with the value obtained by multiplying that fraction by the item profit.
• At the end of the cycle return the result.

We can see the implementation of the above steps in the following code snippet:

import java.util.Arrays;
import java.util.Comparator;

import org.junit.jupiter.api.Test;
 

public class FractionalKnapSack {
     
    private static double getMaximumProfit(Item[] items, double capacity)
    {

        Arrays.sort(items, new Comparator<Item>() {
            @Override
            public int compare(Item item1, Item item2)
            {
                double fraction1 = item1.getProfit() / item1.getWeight();
                double fraction2 = item2.getProfit() / item2.getWeight();
 
                if (fraction1 < fraction2) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });
 
        double maxProfit = 0;
 
        for (Item item : items) {
 
            int w = item.getWeight();
            int p = item.getProfit();
 
            if (capacity - w >= 0) {
                capacity = capacity - w;
                maxProfit += p;
            } else {
                double fraction = (capacity / w);
                maxProfit += (p * fraction);
                capacity = capacity - (w * fraction);
                break;
            }
        }
 
        return maxProfit;
    }

    @Test
    public void fractionalKnapSackTest() throws Exception {
        FractionalKnapSack fractionalKnapSack = new FractionalKnapSack();
        Item[] arr = { fractionalKnapSack.new Item(10, 5), fractionalKnapSack.new Item(20, 15), fractionalKnapSack.new Item(30, 6) };
        int capacity = 10;
        double maxProfit = getMaximumProfit(arr, capacity);
        System.out.println(maxProfit);
    }

    class Item {
        int profit;
        int weight;
        
        public Item(int profit, int weight) {
            this.profit = profit;
            this.weight = weight;
        }
        
        public int getProfit() {
            return profit;
        }

        public int getWeight() {
            return weight;
        }
    }
}

Performance Considerations for the Above 0/1 Knapsack Problem Algorithm

The time complexity of the above algorithm is O(n * logn).

Conclusion

This article shows a way to solve the Fractional Knapsack Problem. The example code is available on GitHub.