Skip to content

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. Include both the 2D tabulation (for clarity) and the space-optimized 1D version (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. Aviation: cargo loading optimization, fuel vs payload tradeoff.

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

Implementation

knapsack

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. Include both the 2D tabulation (for clarity) and the space-optimized 1D version (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. Aviation: cargo loading optimization, fuel vs payload tradeoff.

Complexity

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

knapsack 

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

Source code in src/algo/dp/knapsack.py 
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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):
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)

    return dp[capacity]

knapsack_2d 

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

Source code in src/algo/dp/knapsack.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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]
tests/dp/test_knapsack.py
"""Tests for 0/1 knapsack."""

from algo.dp.knapsack import knapsack, knapsack_2d


class TestKnapsack:
    def test_basic(self) -> None:
        assert knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9

    def test_zero_capacity(self) -> None:
        assert knapsack([1, 2], [10, 20], 0) == 0

    def test_single_item_fits(self) -> None:
        assert knapsack([5], [10], 5) == 10

    def test_single_item_too_heavy(self) -> None:
        assert knapsack([5], [10], 4) == 0

    def test_all_items_fit(self) -> None:
        assert knapsack([1, 2, 3], [6, 10, 12], 10) == 28

    def test_empty(self) -> None:
        assert knapsack([], [], 10) == 0


class TestKnapsack2D:
    def test_matches_1d(self) -> None:
        weights = [1, 3, 4, 5]
        values = [1, 4, 5, 7]
        assert knapsack_2d(weights, values, 7) == knapsack(weights, values, 7)

    def test_basic(self) -> None:
        assert knapsack_2d([2, 3, 4, 5], [3, 4, 5, 6], 5) == 7

    def test_zero_capacity(self) -> None:
        assert knapsack_2d([1], [5], 0) == 0

    def test_no_items(self) -> None:
        assert knapsack_2d([], [], 5) == 0

Implement it yourself

Run: just challenge dp knapsack

Then implement the functions to make all tests pass. Use just study dp for watch mode.

Reveal Solution

knapsack

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. Include both the 2D tabulation (for clarity) and the space-optimized 1D version (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. Aviation: cargo loading optimization, fuel vs payload tradeoff.

Complexity

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

knapsack 

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

Source code in src/algo/dp/knapsack.py 
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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):
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)

    return dp[capacity]

knapsack_2d 

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

Source code in src/algo/dp/knapsack.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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]