Fractional Knapsack Problem

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 :

Output :

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.

As discussed above, for the $i^{th}$ item we have $weight_i + 1$ choices, and hence the total number of possibilities is KaTeX parse error: $ within math mode. Therefore, the time complexity of the brute force approach is $O(\prod_{i=0}^{n-1} (\text{weight}_i + 1))$

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

Java Implementation

Output :

C++ Implementation

Output :

Python Implementation

Output :

C# Implementation

Output :

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)$.

Bonus Tip

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.