Unbounded fractional knapsack problem in Python

In this blog, we are going to learn the unbounded fractional knapsack problem in Python. It is a classic greedy problem. Almost every algorithm course covers this problem. So let’s jump right into it.

Problem Statement

There are n items. And each item is associated with some weights and values. Our task is to put these items in a knapsack, which can hold a maximum weight of W. We can put the same item multiple times, and also put a fraction of the item.

Explanation

We use a greedy approach to solve this problem. We define the function fracKnapsack() to solve this problem. This function takes the weight array, the value array and the maximum capacity of the knapsack as arguments.

First, we traverse the entire list to find the item which has the largest ratio of value to weight. After that, we fill the entire knapsack with the same element which has the largest value to weight ratio. And then, we return the maximum value, i.e multiplication of maximum ratio and the maximum weight of the knapsack. Below is the implementation of this approach.

Solution

Below is the code in Python for unbounded fractional knapsack problem in Python:

def fracKnapsack(wt,val,W):
    n = len(wt)
    if n == 0:
        return 0
    else:
        maxRatioIndex = -1
        maxRatio = -1
        for i in range(n):
            if val[i]/wt[i] > maxRatio:
                maxRatioIndex = i
                maxRatio = val[i]/wt[i]
    maxVal = maxRatio*W
    return maxVal
   
print("Enter the values :")
val = list(map(int,input().split(' ')))
print("Enter the weights :")
wt = list(map(int,input().split(' ')))
W = int(input("Enter the maximum capacity :")

print("The answer is :",fracKnapsack(wt, val, W))

Output

Enter the values :
10 17 24 19 
Enter the weights :
5 9 10 7 
Enter the maximum capacity :50
The answer is 135.71428571428572

Also read: 0/1 knapsack algorithm in Python

For any queries, please comment below.

Thank you.