Knapsack

Problem

Given n items, each with a weight and value, and a knapsack with a weight capacity W, choose items to maximize total value without exceeding capacity. Each item can be taken at most once.

Approach

Classic DP. knapsack_2d is the full tabulation (for clarity); knapsack is the space-optimized 1D alternate (iterate capacity backwards to avoid reusing items in the same row).

When to Use

Resource allocation with constraints — "maximize value under weight limit", "subset sum", "budget allocation". 0/1 variant for items used at most once.

Complexity

Time	O(n * W)
Space	O(n * W) for 2D, O(W) for 1D

Source

"""0/1 Knapsack — maximize value within weight capacity.

Problem:
    Given n items, each with a weight and value, and a knapsack with
    a weight capacity W, choose items to maximize total value without
    exceeding capacity. Each item can be taken at most once.

Approach:
    Classic DP. knapsack_2d is the full tabulation (for clarity);
    knapsack is the space-optimized 1D alternate (iterate capacity
    backwards to avoid reusing items in the same row).

When to use:
    Resource allocation with constraints — "maximize value under weight
    limit", "subset sum", "budget allocation". 0/1 variant for items
    used at most once.

Complexity:
    Time:  O(n * W)
    Space: O(n * W) for 2D, O(W) for 1D
"""

from collections.abc import Sequence


def knapsack_2d(
    weights: Sequence[int],
    values: Sequence[int],
    capacity: int,
) -> int:
    """Return the maximum value achievable using 2D DP table.

    >>> knapsack_2d([1, 3, 4, 5], [1, 4, 5, 7], 7)
    9
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)

    return dp[n][capacity]


# --- space-optimized 1D alternate (rolling array over a 2D table) ---
def knapsack(
    weights: Sequence[int],
    values: Sequence[int],
    capacity: int,
) -> int:
    """Return the maximum value achievable using 1D space optimization.

    >>> knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)
    9
    """
    dp = [0] * (capacity + 1)

    for w, v in zip(weights, values, strict=True):
        # capacity walked high-to-low so dp[c - w] still holds last row's
        # (item i-1) value -- forward iteration would let one item get
        # counted twice in the same pass (unbounded, not 0/1)
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)

    return dp[capacity]