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.

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

and corresponding values **weights**

of **values**

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

.**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Ã—2 ^{n})** 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(2**.

^{n})## 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`and`

weights`in descending order of value/weight(v/w).`

values

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.