# Fractional Knapsack Problem

This problem can be solved using the **Greedy Approach**.

**Goal**: Given a knapsack that has a maximum capacity W, and a set of items with corresponding values and weights, we must choose items in such a way that the total value is maximum, and their total weight doesn't exceed W. Since this is the *fractional* knapsack problem, we can choose parts (fractions) of the items instead of the entire items.

**Algorithm**:

1. Calculate the value/weight ratio for all the items
2. Sort items according to this ratio in descending order
3. Take the item with the **highest** ratio and keep adding items till we can't add the next item as a whole
4. Add a part (fraction) of the next item so as to completely fill the knapsack
5. Calculate total value of items in knapsack accordingly

**Example**:

* W = 50
* Items: A, B, C
* Weights: 10, 20, 30
* Values: 60, 100, 120

Calculating v/w ratios: 6, 5, 4

Sort items according to this ratio in descending order: A, B, C

Items added to the knapsack: A (w=10), B (w=20), C (w=50-(10+20)=20 i.e. 2/3rds)

Total value of added items: 60 + 100 + (2/3)\*120 = 240

**Time Complexity**: O(nlgn)