×

Search anything:

# Fractional Knapsack problem

#### Algorithms Greedy Algorithms knapsack problem Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored fractional knapsack problem with examples. We have covered multiple approaches to solve this.

1) Problem Statement
2) Naive Approach
3) Greedy Approach
4) Conclusion

Pre-requisites:

## 1) Problem Statement

Given arrays of weights `weights` and corresponding values `values` of `n` items.These items are to be kept in a knapsack such that the total profit is maximized and the sum of weights of items kept in the knapsack must not exceed knapsack capacity `c`.

Unlike 01 knapsack ,where an item can be included wholly or cannot, in fractional knapsack problem items can broken/fractioned as per requirement hence the name fractional knapsack.

Ex: (01 knapsack)

c=20
weights = [18,15,10]
values = [25,24,15]

The maximum profit that can be obtained is 25 (By considering the first item)
Solution vector=[1,0,0]

Ex: (Fractional knapsack)

c=20
weights = [18,15,10]
values = [25,24,15]
The maximum profit that can be obtained is 31.5 (By considering the second item and half of third item)
Solution vector=[0,1,1/2]

## 2) Naive Approach

This approach involves trying all possible subsets of items and fractions and keeps track of the maximum profit obtained.

ALGORITHM

-> Create a visited array to keep track of visited items.
-> Backtrack(item)
1.If the current knapsack value is greater than maximum profit seen so far update it.
2.If every item is visited the terminate the function.
3.Iterate through each item
3.1. If the item is already visited the go for the next item.
3.2. If on adding the item to the knapsack its weight exceeds its capacity then it can't be added wholly.A fraction of it is to be added.
Mark as visited
Backtrack(next item)
3.3. If on adding the item to the knapsack its weight becomes less than or equal to its capacity then it can be added wholly.
Mark as visited
Backtrack(next item)
3.4. Don't include the current item.
Mark as visited
Backtrack(next item)
-> Keep track of the maximum profit.

### Implementation

``````#function to check whether every item is visited or not
def is_every_item_visited(visited):
for x in visited:
if x==False:
return False
return True
def fractional_knapsack(currWeight,currValue,vector,visited):
global resValue,resWeight,resVector
#if the current knapsack weight is less than or equal to knapsack capacity
if currWeight<=c:
#if current knapsack profit is greater than maximum profit obtained so far then update
if currValue>resValue:
resValue=currValue
resWeight=currWeight
resVector=vector[:]
# if every item is visited then terminate the function
if is_every_item_visited(visited):
return
#loop through each item
for i in range(n):
# if an item is visited then no need to process it again
if visited[i]:
continue
#if including an item exceeds the knapsack capacity then include a fraction of it
if currWeight+weights[i]>c:
frac=(c-currWeight)/weights[i]
incWeight=frac*weights[i]
incValue=frac*values[i]
vector[i]=frac # indicate what fraction of item is taken
visited[i]=True # mark the item as visited
fractional_knapsack(currWeight+incWeight,currValue+incValue,vector,visited)
# backtrack
visited[i]=False
vector[i]=0
#if including an item doesn't exceed the knapsack capacity then include it wholly
else:
vector[i]=1 # indicate that item is taken wholly
visited[i]=True# mark the item as visited
fractional_knapsack(currWeight+weights[i],currValue+values[i],vector,visited)
# backtrack
visited[i]=False
vector[i]=0

#don't include the item and check for further items
visited[i]=True
fractional_knapsack(currWeight,currValue,vector,visited)
visited[i]=False

weights=[2,3,5,7,1,4,1]
values=[10,5,15,7,6,18,3]
n=len(weights)
resValue=0
# track maximum profit
resWeight=0
# track weight of the knapsack for which maximum profit is obtained
resVector=[]
# track to get an idea about which item is included
c=15
# knapsack capacity

fractional_knapsack(0,0,[0 for i in range(n)],[False for i in range(n)])
print("Knapsack weight:",resWeight)
print("Maximum profit:",resValue)
print("Solution vector:",resVector)
``````

Output:

``````Knapsack weight: 15.0
Maximum profit: 55.333333333333336
Solution vector: [1, 0.6666666666666666, 1, 0, 1, 1, 1]
``````

Time Complexity:

The naive approach takes O(n×2n) time complexity as the algorithm iterates over every item O(n) and for every item it has two choices either to include or to exclude the item O(2n).

## 3) Greedy Approach

The greedy approach involves sorting the items in descending order of value/weight (v/w) and then it keeps including the items in the knapsack i.e., the first item, then second item and so on.

ALGORITHM

1. Sort the arrays `weights` and `values` in descending order of value/weight(v/w).
2. For each item taken
2.1. If on adding the item to the knapsack its weight exceeds its capacity then it can't be added wholly.A fraction of it is to be added.
2.2. If on adding the item to the knapsack its weight doesn't exceed its capacity then it can be added wholly.
3. Repeat step-2 until a fraction of item is included or no further item can be included.
4. Keep track of the maximum profit.

EXAMPLE

Given data

weights = [1,2,4,5,1,3,7]
values = [6,10,18,15,3,5,7]
indices = [4,0,5,2,6,1,3]
c = 15

Variables that will be used

currKnapsackWeight = 0
maxProfit = 0
vector = [0,0,0,0,0,0,0]

Take 1st item

w = 1 v = 6 index = 4
currKnapsackWeight + w = 1 ≤ c (Include the item wholly)
currKnapsackWeight = currKnapsackWeight + w = 0 + 1 = 1
maxProfit = maxProfit + v = 0 + 6 = 6
vector = [0,0,0,0,1,0,0]

After considering 1st item

currKnapsackWeight = 1   maxProfit = 6

Take 2nd item

w = 2 v = 10 index = 0
currKnapsackWeight + w = 1 + 2 = 3 ≤ c (Include the item wholly)
currKnapsackWeight = currKnapsackWeight + w = 1 + 2 = 3
maxProfit = maxProfit + v = 6 + 10 = 16
vector = [1,0,0,0,1,0,0]

After considering 2nd item

currKnapsackWeight = 3   maxProfit = 16

Take 3rd item

w = 4 v = 18 index = 5
currKnapsackWeight + w = 3 + 4 = 7 ≤ c (Include the item wholly)
currKnapsackWeight = currKnapsackWeight + w = 3 + 4 = 7
maxProfit = maxProfit + v = 16 + 18 = 34
vector = [1,0,0,0,1,1,0]

After considering 3rd item

currKnapsackWeight = 7   maxProfit = 34

Take 4th item

w = 5 v = 15 index = 2
currKnapsackWeight + w = 7 + 5 = 12 ≤ c (Include the item wholly)
currKnapsackWeight = currKnapsackWeight + w = 7 + 5 = 12
maxProfit = maxProfit + v = 34 + 15 = 49
vector = [1,0,1,0,1,1,0]

After considering 4th item

currKnapsackWeight = 12   maxProfit = 49

Take 5th item

w = 1 v = 3 index = 6
currKnapsackWeight + w = 12 + 1 = 13 ≤ c (Include the item wholly)
currKnapsackWeight = currKnapsackWeight + w = 12 + 1 = 13
maxProfit = maxProfit + v = 49 + 3 = 52
vector = [1,0,1,0,1,1,1]

After considering 5th item

currKnapsackWeight = 13   maxProfit = 52

Take 6th item

w = 3 v = 5 index = 1
currKnapsackWeight + w = 13 + 3 = 16 > c (Can't include wholly.Hence, include fractionally)
fraction = ( c - currKnapsackWeight ) / w = ( 15 - 13 ) / 3 = 2 / 3 = 0.666666
fractionalWeight = w × fraction = 3 × 0.666666 = 1.999998
fractionalValue = v × fraction = 5 × 0.666666 = 3.33333
currKnapsackWeight = currKnapsackWeight + fractionalWeight = 13 + 1.999998 = 14.999998
maxProfit = maxProfit + fractionalValue = 52 + 3.33333 = 55.33333
vector = [1,0.666666,1,0,1,1,1]

After considering 6th item

currKnapsackWeight = 14.999998   maxProfit = 55.33333

Hence the Maximum Profit obtained is 55.33333 and solution vector is [1,0.666666,1,0,1,1,1].

### Implementation

``````#include<bits/stdc++.h>
using namespace std;
struct item
{
int weight;
int value;
int index;
};
//comparator function is used to sort the array
//in decreasing order of value/weight
bool comparator(struct item item1,struct item item2)
{
return (item1.value/item1.weight)>(item2.value/item2.weight);
}
int main()
{
struct item items[]={{2,10,0},{3,5,1},{5,15,2},{7,7,3},{1,6,4},{4,18,5},{1,4,6}};//{weight,value,index};
//here index is used in 'items' array because after sorting the array might be shuffled
//hence to print whether the item is included or not we keep track of indices.
int n=sizeof(items)/sizeof(items);
//'inclusion' array is used to get an idea about which item is included
double inclusion[n];
//initially none of the items is included hence we fill the 'inclusion' array with 0s indicating the same
memset(inclusion,0,sizeof(inclusion));
//knapsack capacity
int c=15;
//track maximum profit
double maxProfit=0;
//sorting the 'items' array in descending array of value/weight
sort(items,items+n,comparator);
//track current knapsack capacity
double currKnapsackWeight=0;
for(int i=0;i<n;i++)
{
//if item can't be included wholly
if(currKnapsackWeight+items[i].weight>c)
{
//take a fraction of it
double frac=(c-currKnapsackWeight)/items[i].weight;
//include fractional weight of the item taken
currKnapsackWeight+=items[i].weight*frac;
//include that value which we get by taking fraction of item
maxProfit+=items[i].value*frac;
//indicate what fraction of item is taken
inclusion[items[i].index]=frac;
break;//as we taken a fraction no further items can be included
}
//as including the current item don't exceed the knapsack capacity it can be taken wholly
else
{
//include weight of the item
currKnapsackWeight+=items[i].weight;
//include value of the item
maxProfit+=items[i].value;
//as we take item wholly we indicate its inclusion as 1
inclusion[items[i].index]=1;
}
}
cout<<"Knapsack weight:"<<currKnapsackWeight<<endl;
cout<<"Maximum profit:"<<maxProfit<<endl;
cout<<"Solution vector:";
for(int i=0;i<n;i++)
{
cout<<inclusion[i]<<" ";
}
}
``````

Output:

``````Knapsack weight:15
Maximum profit:55.3333
Solution vector:1 0.666667 1 0 1 1 1
``````

## 4) Conclusion

The algorithm uses sorting to sort the items which takes O(n×logn) time complexity and then loops through each item which takes O(n).Hence summing up to a time complexity of O(n×logn+n)=O(n×logn).

If the items are already sorted then it takes O(n) time complexity.

With this article at OpenGenus, you must have the complete idea of Fractional Knapsack problem.