# 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:

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:

## 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).