Fractional Knapsack

Introduction

The Fractional Knapsack problem is a classic optimization problem where a thief can take fractions of items (not just whole items) to maximize the total value in a knapsack with limited capacity. Unlike the 0/1 Knapsack problem (which is NP-hard), the Fractional Knapsack has an elegant greedy solution that runs in O(n log n) time.

The key difference from the 0/1 variant is that items are divisible -- think of bulk goods like gold dust, grain, or liquid rather than indivisible objects. This divisibility property is precisely what makes the greedy approach optimal: we can always take exactly as much of the best remaining item as the knapsack can hold.

Problem Definition

Given n items, each with weight w_i and value v_i, and a knapsack with capacity W, choose fractions x_i (where 0 <= x_i <= 1) for each item to maximize:

maximize: sum(x_i * v_i) for i = 1 to nsubject to: sum(x_i * w_i) <= W 0 <= x_i <= 1 for all i

Greedy Strategy

The greedy approach computes the value-to-weight ratio (v_i / w_i) for each item, sorts items in decreasing order of this ratio, and greedily adds items to the knapsack:

Pseudocode

procedure FractionalKnapsack(items, W): for each item i: ratio[i] = items[i].value / items[i].weight sort items by ratio in decreasing order totalValue = 0 remainingCapacity = W for each item i in sorted order: if items[i].weight <= remainingCapacity: // Take the whole item totalValue = totalValue + items[i].value remainingCapacity = remainingCapacity - items[i].weight else: // Take a fraction fraction = remainingCapacity / items[i].weight totalValue = totalValue + fraction * items[i].value remainingCapacity = 0 break return totalValue

The greedy choice is intuitive: always take the item that gives the most value per unit weight. Since we can take fractions, there is no "waste" from partially filling the knapsack, and the locally optimal choice at each step leads to the globally optimal solution.

Proof of Optimality

The proof uses an exchange argument:

1. Let G be the greedy solution and O be any optimal solution.
2. Consider the first item i where G and O differ in the fraction taken.
3. Since G takes items in decreasing ratio order, item i has ratio at least as high as any item taken more in O.
4. We can increase x_i in O and correspondingly decrease some x_j (where j has a lower ratio) without violating the capacity constraint, while not decreasing total value.
5. Repeating this exchange transforms O into G without losing value, proving G is optimal.

The greedy algorithm satisfies both conditions required for greedy optimality:

• Greedy choice property: There exists an optimal solution that includes the greedy first choice.
• Optimal substructure: After making the greedy choice, the remaining subproblem is a smaller instance of the same problem.

Worked Example

Knapsack capacity W = 50. Items:

Sorted by ratio: A (6.0), B (5.0), C (4.0).

Step 1: Take all of A. Weight used: 10. Value: 60. Remaining capacity: 40.

Step 2: Take all of B. Weight used: 30. Value: 160. Remaining capacity: 20.

Step 3: Take 20/30 = 2/3 of C. Weight used: 50. Value: 160 + (2/3)*120 = 160 + 80 = 240.

Result: Maximum value = 240, taking all of A, all of B, and 2/3 of C.

Complexity Analysis

Space complexity: O(1) extra beyond the input (or O(n) if ratios are stored separately).

Note: Using a linear-time selection algorithm to find the "critical" item (the one that is fractionally included) can reduce the time to O(n), but this is rarely needed in practice.

Implementation

def fractional_knapsack(items, capacity): # items is a list of (weight, value) tuples # Sort by value/weight ratio descending items.sort(key=lambda x: x[1]/x[0], reverse=True) total_value = 0.0 remaining = capacity for weight, value in items: if weight <= remaining: total_value += value remaining -= weight else: fraction = remaining / weight total_value += fraction * value remaining = 0 break return total_value# Exampleitems = [(10, 60), (20, 100), (30, 120)]print(fractional_knapsack(items, 50)) # Output: 240.0

Comparison with 0/1 Knapsack

The greedy approach does not work for the 0/1 Knapsack problem. Consider: items with (weight=10, value=60), (weight=20, value=100), (weight=30, value=120), capacity=30. The greedy approach selects item A (ratio 6.0) then cannot fit B or C completely. Greedy value = 60. But taking item C alone gives value 120, which is optimal.

The fractional variant avoids this trap because it can take partial items. When the best-ratio item does not fully use the capacity, the fractional version fills the remaining space with parts of other items. The 0/1 version cannot do this and may "waste" capacity.

The fractional knapsack solution is always an upper bound on the 0/1 knapsack solution with the same inputs. This fact is used in branch-and-bound algorithms for the 0/1 variant: the fractional solution provides a bound to prune the search tree.

Applications

• Resource Allocation: Distributing a fixed budget across investments to maximize return, where fractional investments are allowed.
• Loading Problems: Loading cargo onto a ship or truck where items like grain or liquid can be divided.
• CPU Scheduling: Allocating processor time among tasks proportionally to their priority-to-time ratios.
• Network Bandwidth: Allocating bandwidth among competing data flows based on value-per-byte.
• Branch-and-Bound: The fractional knapsack solution serves as a relaxation bound in integer programming solvers for the 0/1 knapsack and related problems.

References

• Dantzig, G. B. "Discrete-Variable Extremum Problems." Operations Research, vol. 5, 1957, pp. 266-277.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to Algorithms." MIT Press, Chapter 16, 2009.
• Kellerer, H., Pferschy, U., and Pisinger, D. "Knapsack Problems." Springer, 2004.
• Martello, S. and Toth, P. "Knapsack Problems: Algorithms and Computer Implementations." John Wiley, 1990.