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.
Leave a Reply