Fractional Knapsack
← Back to Classic Problems (Greedy)
A variant of the knapsack problem where items can be divided. The greedy strategy of selecting items by highest value-to-weight ratio produces an optimal solution. O(n log n) time after sorting. Contrast with the 0/1 Knapsack which requires DP.