Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explored fractional knapsack problem with examples. We have covered multiple approaches to solve this.
| Table of Contents |
|---|
| 1) Problem Statement |
| 2) Naive Approach |
| 3) Greedy Approach |
| 4) Conclusion |
Pre-requisites:
- Solving Unbounded Knapsack Problem using Dynamic Programming
- 0-1 Knapsack Problem (Integral Knapsack)
- Bin Packing problem
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
weightsandvaluesin 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[0]);
//'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.
