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 :

- Do not take any fraction of the $i^{th}$ item.
- Take the item as a whole.
- 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 of`40`

and the capacity of the knapsack is now reduced to`50`

. Then we pick the $3^{rd}$ item as a whole, after which we obtain a value of`120`

and the capacity of the knapsack is now reduced to`30`

.

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

Item no. | Weight | Value |
---|---|---|

1 | 1 | 3 |

2 | 1 | 6 |

3 | 1 | 5 |

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.

$\text{Item}_1$ | $\text{Item}_2$ | $\text{Item}_3$ | Total Value |
---|---|---|---|

0 | 0 | 0 | 0 |

0 | 0 | 1 | 5 |

0 | 1 | 0 | 6 |

0 | 1 | 1 | 11 |

1 | 0 | 0 | 3 |

1 | 0 | 1 | 8 |

1 | 1 | 0 | 9 |

1 | 1 | 1 | 14 |

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 :

- Picking the items with the largest values first.
- Picking the items with the lowest weights first.
- 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 :**

Item No. | Weight | Value |
---|---|---|

1 | 10 | 40 |

2 | 30 | 20 |

3 | 20 | 80 |

4 | 50 | 70 |

5 | 20 | 50 |

**Capacity (W) :** 70

### Approach – 1 : Picking Items with the Largest Value

Item No. | Weight | Value | Remaining Space |
---|---|---|---|

3 | 20 | 80 | 70 – 20 = 50 |

4 | 50 | 70 | 50 – 50 = 0 |

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

### Approach – 2 : Picking Items with the Smallest Weight

Item No. | Weight | Value | Remaining Space |
---|---|---|---|

1 | 10 | 40 | 70 – 10 = 60 |

3 | 20 | 80 | 60 – 20 = 40 |

5 | 20 | 50 | 40 – 20 = 20 |

2 | 30 | $\frac{20}{30} * 20 = 13.33$ | 20 – 20 = 0 |

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

Item No. | Weight | Value | $\frac{Value}{Weight}$ |
---|---|---|---|

1 | 10 | 40 | $\frac{40}{10} = 4$ |

2 | 30 | 20 | $\frac{20}{30} = 0.66$ |

3 | 20 | 80 | $\frac{80}{20} = 4$ |

4 | 50 | 70 | $\frac{70}{50} = 1.4$ |

5 | 20 | 50 | $\frac{50}{20} = 1.5$ |

**Now picking items as follows :**

Item No. | Weight | Value | Remaining Space |
---|---|---|---|

1 | 10 | 40 | 70 – 10 = 60 |

3 | 20 | 80 | 60 – 20 = 40 |

5 | 20 | 50 | 40 – 20 = 20 |

4 | 50 | $\frac{70}{50} * 20 = 28$ | 40 – 20 = 0 |

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.

- Add
**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.