﻿==================================================
3. FRACTIONAL KNAPSACK (GREEDY)
==================================================

ALGORITHM:
1. Calculate value/weight ratio for every item.
2. Sort items in decreasing order of ratio.
3. Initialize the remaining knapsack capacity.
4. Select the item with the highest ratio.
5. If the item fits, take it completely.
6. Otherwise, take the fraction that fits.
7. Calculate the total maximum value.

FORMULA:
Ratio = Value / Weight

Total Value = Sum(Value[i] * Fraction[i])

RECURRENCE:
Not recursive. Uses Greedy technique.

TIME COMPLEXITY:
Sorting   : O(n log n)
Selection : O(n)
Overall   : O(n log n)
Space     : O(n)