Fractional Knapsack problem

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×2ⁿ) 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ⁿ).

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[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.