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

- Calculate the value/weight ratio for all the items
- Sort items according to this ratio in descending order
- Take the item with the
**highest**ratio and keep adding items till we can't add the next item as a whole - Add a part (fraction) of the next item so as to completely fill the knapsack
- 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)