Fractional Knapsack
Sort by value per weight. Take whole items until one must be split to fill the remaining room exactly.
Fractional Knapsack: The classic three items
Item a, 10 kg worth 60 (6 per kg), room 50. It fits whole: take it all, value 60.0, room 40.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(1)