AlgoScope

Fractional Knapsack

Sort by value per weight. Take whole items until one must be split to fill the remaining room exactly.

Greedy, algorithm, intermediate
Take item a whole.abcwvv/wtake102030601001206541
Take item a whole.abcwvv/wtake102030601001206541

Fractional Knapsack: The classic three items

Decision, step 2 of 5

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)