Fractional Knapsack Problem: Greedy Approach

Problem Statement

Given the weights W and values V of N items which are to be inserted in the knapsack which can bear the weight upto K. Insert maximum value in the knapsack with weight not greater than K. Every item can be inserted in fractional manner also( i.e, we can break the iteam to maximise the value in the knapsack).

Examples

For better understanding of the problem statment, lets look at the below example:

Input: arr={(20,4),(63,7),(40,8),(30,5)} and K= 18

Explanation: Array is of format {(Value,Weight)}. To maximise the value in the bag with weight not more than K and also breaking of items is allowed. So, we can use a greedy approach in this problem. Firstly, find the ratio of Value/Weight and using this ratio. Arrange the items to maximise the profit. The ratios of the given input in the descending order is as follows:

Item 2(W/V)	Item 4(W/V)	Item 1(W/V)	Item 3(W/V)
63/7=9	30/5=6	20/4=5	40/8=5

The knapsack capacity is given as K= 18. So, accordingly we can fit upto:

Item 2 weight +Item 4 weight + Item 1 weight + 1/4(Item 3 weight)= 18

Therefore. The value of the knapsack is 63+30+20+¼(40)= 123

Output: 123

Greedy Approach

In the above example, we have discussed to obtain the maximum value in the knapsack. We need to find the ratio of Value/Weight and we need to return the maximum value of the knapsack obtained. Finding all the ratios and arranging them in descending order and adding into the knapsack without exceeding the capacity of the knapsack. This is performed greedily by breaking the iteams whenever needed. This can be clearly explained in the below implemented code:

# Python Program for fractional knapsack
# Class which defined the structure of an item which stores weight and corresponding value of item from the given input
class Item:
def __init__(self, value, weight):
# constructor initialisation
self.value = value
self.weight = weight

# Greedy function for finding the maximum value in the knapsack.
def fractionalKnapsack(K, arr):

# Sorting Item on basis of ratio in descending order
arr.sort(key=lambda x: (x.value/x.weight), reverse=True)

# Final value in knapsack
Value_Knapsack = 0.0

# Looping through all Items such that knapsack doesnt exceed its capacity
for i in arr:
# If adding Item in the knapsack doesnt exceed the capacity add it in the knapsack else return the final value
if i.weight <= K:
K -= i.weight
Value_Knapsack += i.value

# If we can't add current Item completely, add the fractional value until it does not exceed the capacity K
else:
Value_Knapsack += i.value * K / i.weight
break

# Returning final value of the knapsack
return Value_Knapsack

# Driver Code
# Capacity of the knapsack
K = 18
# input weight and value array
arr = [Item(20, 4), Item(63, 7), Item(40, 8), Item(30,5)]

# Greedy funciton is called to obtain the final value
ans = fractionalKnapsack(K, arr)
print(ans)

write your code here: Coding Playground

Complexity Analysis

Time Complexity: O( N*LogN), where N is the number of items given.

Finding the ratio and sorting them in the descending order using merge sort, has the overall time complexity of O(N* Log N).

Space Compleity: O(N), where N is the number of items given.

Extra space is needed during the merge sort for arranging the ratios in descending order.

Conclusion

In the fractional knapsack, to maimise the value in the knapsack by not exceeding the capacity of the knapsack is resolved using a greedy approach of time complexity O(N LogN) and space complexity of O(N).