## 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

*. We have to fill a knapsack of capacity*

**p***, 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*

**W****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

*culated 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).*

*, cal**{*10, 5}## 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
to the lowest.**p/w** - Use two variables to store the current result and remaining capacity and initialize them to
and*0**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.