Fractional Knapsack Problem using Greedy Approach in Python

By Tanay R Dandekar

In this article, we are going to learn about the fractional knapsack problem and its implementation in python using the greedy approach.

Problem Statement:

In the Fractional Knapsack Problem, we have given a list of items, their weight, and profit associated with items. Our task is to put a set of items in the knapsack so that the total profit value of items in it is maximum and its total weight should be less than or the same as the given capacity. Also, we can put fractions of items in the sack.

Steps to solve the problem:

1. Take the weight and profit of each item and maximum weight.
2. Calculate the profit per weight for each item.
3. Sort the items according to profit per weight in descending order.
4. Start putting items in the sequence same as items sorted according to profit per weight in decreasing order. If an item can not be put as a whole, put a suitable fraction of it so that we will get the maximum total profit.

Python code:

#Fractional Knapsack Problem
#Getting input from user
n=int(input("Enter no. of items: "))
maxwt=int(input("Maximum weight: "))
profit=list(map(int, input("Enter profit value of items: ").split()))
weight=list(map(int, input("Enter weight of items: ").split()))

#Initializing total weight in sack as wt and maximum profit value as max_profit
wt=0
max_profit=0

#Calculating profit value per weight value for objects
ppw = []
for i in range(n):
    ppw.append(profit[i]/weight[i])

#Creating sequence for putting objects in the sack
order=[] #order list contains list index of object in decreasing order of profit value per weight
for i in range(n):
    order.append(ppw.index(max(ppw)))
    ppw[ppw.index(max(ppw))]=0

i=0
#Putting items of higher profit value per weight in sack
print("\nItems in Knapsack: ")
print("Item\tWeight\tProfit Value\tFraction")
while wt!=maxwt:
    if (wt+weight[order[i]])<=maxwt:
        max_profit+=profit[order[i]]
        wt+=weight[order[i]]
        print("%d\t%d\t%d\t\t1"%(order[i]+1,weight[order[i]],profit[order[i]]))
    else:
        fraction = (maxwt-wt)/weight[order[i]]
        value = profit[order[i]]*fraction
        max_profit+= value
        wt+=(maxwt-wt)
        print("%d\t%d\t%0.2f\t\t%0.2f"%(order[i]+1,weight[order[i]],value,fraction))
    i+=1

print("\nMaximum profit= %0.2f"%max_profit)

 

Output:

Thank you