0/1 knapsack: choose the items, not just the best value

The single item worth 5 is tempting, but it leaves too little room for either other item. The pair worth 7 is better. Trying every subset would find it; the table method avoids solving the same smaller choice repeatedly.

Compare taking an item with leaving it#

In this illustrative problem, weights are positive integers, values are nonnegative integers and capacity is a nonnegative integer. Every item is available once. The bag may have unused capacity; the selected total must only stay within its limit.

Let dp[i][c] mean the best value available from the first i items with capacity c. With no items, every answer is zero. For the next item, compare two possibilities: leave it and keep the earlier answer, or take it and add its value to the best answer for the remaining space.

Both choices use the previous row, which contains only earlier items. That is how the table prevents a second copy of the item under consideration.

item weight w is too large: dp[i][c] = dp[i-1][c]
otherwise: dp[i][c] = max(dp[i-1][c], value + dp[i-1][c-w])

Saving answers to these smaller problems is called dynamic programming. The important first step is defining what a cell means; the formula then expresses the two allowed choices.

Try the worked example

Bag capacity (0–10) Run example

Read a complete small table#

Use capacity 5 and items A=(weight 2, value 3), B=(3, 4) and C=(4, 5):

Items available	Capacity 0	1	2	3	4	5
none	0	0	0	0	0	0
A	0	0	3	3	3	3
A, B	0	0	3	4	4	7
A, B, C	0	0	3	4	5	7

At capacity 5 in B’s row, leaving B gives 3. Taking B gives its value 4 plus the value 3 available from A at remaining capacity 2. The cell becomes 7.

In C’s row, taking C at capacity 5 gives only 5 + 0: none of the earlier items fits the remaining capacity 1. Leaving C preserves 7. The table did not assume the item with the highest individual value belonged in the answer.

Recover the items and avoid taking one twice#

Start at the bottom-right cell. It equals the value above, so C is not needed for this chosen optimum. Move up. B’s row differs from the row above at capacity 5, so select B and reduce capacity by its weight to 2. A’s row then differs from the empty row, so select A. The resulting set has weight 5 and value 7. When two choices tie, this rule selects one optimum, not every possible optimum.

The full table takes O(nW) time and space for n items and capacity W. When only the value is needed, this Python version keeps one row:

def knapsack_value(items: list[tuple[int, int]], capacity: int) -> int:
    # Each item is (positive integer weight, nonnegative integer value).
    if capacity < 0 or any(w <= 0 or v < 0 for w, v in items):
        raise ValueError("use nonnegative capacity/value and positive weights")
    best = [0] * (capacity + 1)
    for weight, value in items:
        for c in range(capacity, weight - 1, -1):
            best[c] = max(best[c], value + best[c - weight])
    return best[capacity]

The capacity loop runs downwards. With a single item (2, 3) and capacity 4, an upward loop could first write best[2] = 3, then reuse that new value to write best[4] = 6. It would count the same item twice. Running downwards reads the previous item’s results instead and returns 3. This function returns only a value; keep the full table when using the backwards item-recovery method above.

Longest common subsequence also recovers a result from a table of smaller answers. The recursion guide explains the nested calls behind a direct take-or-leave search. Whichever representation you choose, check that the stored state enforces the “at most once” rule rather than merely producing a plausible total.

Questions people also ask

2 QUESTIONS

▸ Must the chosen items fill the bag exactly?

No. The goal is the greatest value without exceeding capacity. Unused capacity is allowed. Requiring an exact total weight changes the initial states and the problem being solved.

▸ Why is O(nW) called pseudo-polynomial?

The work grows with the numeric capacity W, not just the number of digits needed to write it. Adding one binary digit can nearly double W, so a compactly written capacity can still require a very large table.