Fractional Knapsack

Each item has positive weight $w_i$ and nonnegative value $v_i$. Any fraction $x_i\in[0,1]$ may be taken, contributing $x_iw_i$ weight and $x_iv_i$ value.

Greedy rule

Sort by value density $v_i/w_i$ from highest to lowest. Take each item fully until the remaining capacity fits only a fraction of the next item.

def fractional_knapsack(items: list[tuple[float, float]], capacity: float) -> float:
    total = 0.0
    if capacity == 0:
        return total
    for weight, value in sorted(items, key=lambda x: x[1] / x[0], reverse=True):
        amount = min(weight, capacity)
        total += value * (amount / weight)
        capacity -= amount
        if capacity == 0:
            break
    return total

Inputs must reject zero/negative weights; floating-point boundary behavior may also need a tolerance in numerical applications.

Exchange proof

If a feasible solution uses some weight of a lower-density item while a higher-density item remains available, exchanging equal weight between them does not reduce value and normally increases it. Repeating exchanges yields the density-ordered greedy solution.

Cost and boundary

Sorting takes $O(n\log n)$ time; the scan is linear. The proof depends on continuous divisibility and linear value. In 0/1 knapsack an item cannot be partially exchanged, so the same density rule can be suboptimal.

Fractional optimum versus 0/1 optimum

For capacity 6 and (weight,value) items (4,5),(3,3),(3,3), densities are 1.25, 1, 1. Take the first item and two thirds of a weight-3 item: value 5+2=7. In the 0/1 version, density-first takes the weight-4 item and cannot fit another, giving 5; the optimum takes both weight-3 items for 6. The exchange proof works only when the equal-weight exchange is legal.

The function assumes finite inputs, nonnegative capacity and values, and strictly positive weights; type annotations do not validate them. Empty input or zero capacity returns zero. Capacity beyond the total weight takes everything and leaves unused capacity. Sorting allocates O(n) space in Python. Equal densities can be taken in any order without changing the optimum; a numerical tolerance must not silently allow materially exceeding capacity.

assert fractional_knapsack([(4, 5), (3, 3), (3, 3)], 6) == 7
assert fractional_knapsack([], 6) == 0
assert fractional_knapsack([(4, 5)], 0) == 0

Source

• MIT OpenCourseWare: Greedy Algorithms

My reading · Opened notes are remembered in this browser.