Fractional Knapsack
Maximize value in a knapsack by greedily selecting items by value-to-weight ratio.
The Fractional Knapsack Problem
You have a knapsack with a weight capacity W and n items, each with a weight wᵢ and value vᵢ. Unlike the 0/1 Knapsack, you can take fractions of items. The goal is to maximize total value without exceeding capacity W.
The Greedy Strategy
Compute the value-to-weight ratio (vᵢ/wᵢ) for each item and sort in decreasing order. Greedily take as much as possible of the highest-ratio item first, then move to the next.
This greedy approach works here because we can take fractions — there's no commitment cost. If the knapsack fills up mid-item, we simply take the fraction that fits.
Step-by-Step Visualization
Watch items being loaded into the knapsack in order of their value/weight ratio. This example has seven items with different ratios: several are taken fully, one is taken only in part when capacity runs out, and the rest are skipped.
Fractional vs. 0/1 Knapsack
Why greedy fails for 0/1 Knapsack: In the 0/1 variant, you must take an entire item or leave it. The greedy approach can miss the optimal combination. For example, with items (60, 10), (100, 20), (120, 30) and W=50: greedy picks items 1 & 2 (value=160), but items 2 & 3 give value=220.
The 0/1 Knapsack requires Dynamic Programming for optimal solutions.
Pseudocode
The algorithm sorts by ratio then performs a single scan.
1FRACTIONAL-KNAPSACK(items, W)2 for each item i3 ratio[i] = value[i] / weight[i]4 Sort items by ratio descending5 totalValue = 06 remaining = W7 for each item i (in sorted order)8 if weight[i] <= remaining9 take all of item i10 totalValue += value[i]11 remaining -= weight[i]12 else13 fraction = remaining / weight[i]14 totalValue += value[i] * fraction15 remaining = 016 break17 return totalValue
Complexity Analysis
Dominated by the O(n log n) sorting step. The greedy fill loop is O(n). Only O(1) extra space is needed beyond the input.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1)
Sorting dominates; the fill loop is O(n)
Growth Rate Comparison
Interactive Playground
Customize item weights, values, and knapsack capacity. See the greedy solution and how much of each item is taken.