Skip to main content

Fractional Knapsack

Each item has positive weight wiw_i and nonnegative value viv_i. Any fraction xi∈[0,1]x_i\in[0,1] may be taken, contributing xiwix_iw_i weight and xivix_iv_i value.

Greedy rule​

Sort by value density vi/wiv_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
    for weight, value in sorted(items, key=lambda x: x[1] / x[0], reverse=True):
        amount = min(weight, capacity)
        total += amount * (value / 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(nlog⁡n)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.

Source​