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(n(C+1))$.
• Value-only space: $O(C+1)$.
• 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.

Why both choices are needed

Before compression, define D[i,c] using only the first i items. Every feasible optimum either excludes item i, giving D[i-1,c], or includes it, giving v_i + D[i-1,c-w_i] when it fits. These cases are exhaustive, and removing the included item leaves precisely the stated smaller problem. Initialize the no-item row to zero because selecting nothing is allowed; this is not an exact-fill problem.

For weights [2,3], values [3,4], capacity 5, the rows for capacities 0 through 5 are [0,0,0,0,0,0], [0,0,3,3,3,3], then [0,0,3,4,4,7]. Ascending updates would already produce value 6 at capacity 4 from the first item alone, illegally using it twice.

Require integer nonnegative capacity and weights and matching input lengths; zip(..., strict=True) requires Python 3.10+. A zero-weight item is considered once per capacity, so a positive value is added once even at capacity zero. The unbounded-update explanation assumes positive weights: unlimited positive-value zero-weight items would make the optimum unbounded. Empty input returns zero. For capacity 6 and items (weight,value)=(4,5),(3,3),(3,3), density-first 0/1 selection gives 5, but DP finds 6 by taking the two weight-3 items.

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

Source

• CP-Algorithms: Knapsack Problem

My reading · Opened notes are remembered in this browser.