Dynamic programming for the 0/1 knapsack problem

The 0/1 knapsack problem asks you to select a subset of items so their total weight does not exceed a capacity while their total value is as large as possible. Each item can be used once: take it or leave it. That either-or rule distinguishes the problem from unbounded knapsack, in which the same item could be chosen repeatedly, and from fractional knapsack, where part of an item may be taken.

Dynamic programming handles the combinatorial search by reusing answers to smaller subproblems. Its key design choice is a state that captures the information needed for every later decision: which items have been considered and how much capacity remains. From that state, you can derive a transition, establish base cases, implement the table, and analyse its complexity without enumerating all possible subsets.

The problem in practical terms

Picture packing for a bushwalk in the Blue Mountains: a compact tent, a warm jumper, lunch, a charger and a first-aid kit all compete for space in a backpack. A sensible packer assigns a value to each item based on usefulness, while kilograms provide the weight. The mathematical version replaces those judgements with numbers, but the optimisation is the same.

Suppose there are (n) items, with weights (w_1) through (w_n) and values (v_1) through (v_n), plus a capacity (W). The goal is to maximise total value or profit subject to (\sum w_i \leq W), where each index is either zero or one. That binary selection variable is the source of the name 0/1.

Australian examples often use kilos rather than grams, so (W) might be eight kilograms in a simple exercise. In everyday speech, a knapsack may be called a school bag or, for a packed meal, an arvo tucker. At a Woolworths or Coles checkout, unit prices and bulk packs also illustrate why value and weight are separate ideas: a larger package can cost more while still being the better choice per kilogram.

The educational approach on hello ML fits this practical style. Its about page describes a community-written blog that explains computer science openly, so readers can connect the recurrence to implementations and complexity analysis rather than treating code as magic.

Defining the dynamic programming state

Define dp[i][w] as the maximum value obtainable using only the first (i) items with a carrying limit of (w). The (i) dimension removes ambiguity about which choices are available; the (w) dimension records the remaining capacity. Together they form a sufficient state because future decisions depend only on the item index and capacity, not on how that state was reached.

The base case is dp[0][w] = 0 for every capacity: with no items, choosing nothing yields value zero. For positive weights, dp[i][0] is also zero because no item fits. Every other cell can then be filled from smaller subproblems, such as dp[i-1][w] and dp[i-1][w-wi].

The final optimal value is dp[n][W]. An important detail is that (w) means capacity at most (w), not weight exactly equal to (w). Consequently, a solution may leave part of the backpack unused. If an exact-weight variant is required, unreachable states need an explicit sentinel such as negative infinity and a different base case.

Deriving the optimal-substructure recurrence

When considering item (i), every feasible solution falls into one of two cases. It either skips the item, leaving the best result from dp[i-1][w], or takes it, adding (v_i) to the best result from the previous items that fits in capacity (w-w_i). These alternatives are exhaustive and mutually exclusive.

The recurrence is therefore:

if wi > w:
    dp[i][w] = dp[i-1][w]
else:
    dp[i][w] = max(dp[i-1][w], vi + dp[i-1][w-wi])

This is the optimal-substructure step: an optimal solution contains an optimal solution to its smaller residual problem.

The same habit of defining a state before making a choice appears in Gaussian processes for regression, where a prediction depends on the training points and their relationships. It is a different model, but the lesson transfers: a useful state makes valid transitions explicit and keeps the reasoning auditable.

A bottom-up Python implementation

A direct tabulation implementation creates the full two-dimensional table. The outer loop advances through items, while the inner loop covers every capacity from zero to (W).

def knapsack_01(values, weights, capacity):
    if len(values) != len(weights):
        raise ValueError("values and weights must have equal lengths")

    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        value = values[i - 1]
        weight = weights[i - 1]

        for limit in range(capacity + 1):
            dp[i][limit] = dp[i - 1][limit]

            if weight <= limit:
                dp[i][limit] = max(
                    dp[i][limit],
                    value + dp[i - 1][limit - weight]
                )

    return dp[n][capacity]

Each cell copies the skip option before considering the take option. Rows are processed in increasing item order, so dp[i-1] is already complete when row i is calculated. The function returns the best value within the supplied capacity and assumes non-negative integer weights and a non-negative integer capacity.

For example, values [12, 7, 11, 8], weights [4, 3, 5, 2] and capacity 8 return 20. Items with weights 4 and 2 have total weight 6 and total value 20. Leaving two kilograms unused is valid because the table measures value for capacity at most eight.

Reducing memory without changing the answer

Only the previous row is needed to compute the current row, so the table can be compressed into a one-dimensional array. Here, dp[limit] stores the best value found for that capacity while processing items from left to right.

def knapsack_01(values, weights, capacity):
    if len(values) != len(weights):
        raise ValueError("values and weights must have equal lengths")

    dp = [0] * (capacity + 1)

    for value, weight in zip(values, weights):
        for limit in range(capacity, weight - 1, -1):
            candidate = value + dp[limit - weight]
            dp[limit] = max(dp[limit], candidate)

    return dp[capacity]

The inner loop must run backwards, from capacity to weight. A forward loop could read a cell already updated for the current item, allowing that item to be reused and turning the logic into an unbounded-knapsack calculation. Descending order ensures dp[limit-weight] still belongs to the previous item.

The two-dimensional version uses (O(nW)) time and (O(nW)) space; the compressed version uses (O(nW)) time and (O(W)) space. These bounds are pseudo-polynomial because (W) is expressed as a number: a very large capacity can make the table impractical even when the item count is small.

Why the method is correct

Correctness follows by induction over the number of processed items. The empty-item row is correct because no selection can produce positive value. For each later item, the recurrence compares every possible solution’s skip and take branches, each built from an already-correct earlier state. Their maximum is therefore the optimal value for the new state.

In the example, after the weight-4 item, capacities 4 through 8 can achieve 12. After the weight-3 item, capacity 8 can achieve 19 by combining values 12 and 7. Processing the weight-5 item does not improve capacity 8 because it costs 5 and has value 11. The final weight-2 item produces 20 from the earlier value 12 at capacity 6.

Edge cases follow from the same definitions. Empty input returns zero, zero capacity returns zero for positive-weight items, and items heavier than the capacity are skipped. Negative values need no special rule because the skip option retains the previous result. Ties may produce several equally valuable selections, so the value answer does not identify a unique subset.

Practical guidance for learning and applying the method

This pattern appears frequently in LeetCode-style exercises and interviews. Australian developers applying for software roles in Sydney or Melbourne are often judged on clarity as well as a working solution, so explaining the state, recurrence and loop direction demonstrates sound reasoning.

• State the meaning of every table entry before writing code, including whether capacity means “at most” or “exactly”.
• Trace a small example by hand and record the best value after each item is processed.
• Keep the 0/1, unbounded and fractional variants distinct because their transitions and constraints differ.
• Test empty input, zero capacity, oversized items and a solution that does not fill the backpack.
• Report both time and space complexity, including the pseudo-polynomial dependence on capacity.

A reconstruction table can also identify which items were selected, although it trades extra memory for a clearer explanation of the final subset. For related patterns such as recursion, greedy methods and data structures, hello ML’s algorithm guides offer useful comparisons with the same state-based reasoning.

Taken together, dynamic programming turns an exponential selection problem into a systematic table of optimal subproblems. The method remains reliable because the recurrence, implementation order and correctness argument all describe the same constraint precisely.