0/1 Knapsack

Given items with nonnegative integer weights $w_i$ and values $v_i$, choose each item at most once to maximize total value under capacity $C$:

$$\max \sum_i v_i x_i \quad\text{subject to}\quad \sum_i w_i x_i \le C,\qquad x_i\in\{0,1\}.$$

State and transition

Let dp[c] be the best value achievable with processed items and capacity c. For each item, update capacities in descending order:

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values, strict=True):
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

Descending order ensures dp[current - weight] still belongs to the previous item layer, so an item cannot be reused. Ascending order instead implements an unbounded-use transition.

Cost and interpretation

• Time: $O(nC)$.
• Value-only space: $O(C)$.
• Reconstructing selected items needs stored decisions or recomputation.

This runtime is pseudo-polynomial: it is polynomial in numeric capacity $C$, not in the number of bits needed to encode $C$.

Variants are different problems

• Fractional knapsack permits splitting items and has a greedy solution.
• Unbounded knapsack permits unlimited reuse and changes update order.
• Bounded knapsack supplies a finite multiplicity per item.

State the variant before choosing a recurrence.

Source

• CP-Algorithms: Knapsack Problem