Dynamic programming with reconstruction

Prerequisites: Arrays, recurrence relations, and induction.

Learning objectives

• Define a sufficient subproblem state.
• Derive a recurrence and evaluation order.
• Reconstruct and verify an optimal solution.

Define the meaning of each cell

In zero-one knapsack, each item has an integer weight and value; each may be selected at most once. Given integer capacity W, maximize total value without exceeding W. Define D[i,c] as the best value using only the first i items with capacity at most c. This state records exactly the prefix of items available and the remaining resource bound. A table without that sentence has no reliable interpretation.

If item i has weight w_i and value v_i, either omit it or include it. Omitting gives D[i−1,c]. Including is permitted when w_i≤c and gives v_i+D[i−1,c−w_i]. Take the larger of the valid alternatives. Initialize D[0,c]=0 for every capacity and use rows in increasing item order. The recurrence is justified because every feasible solution belongs to exactly one of these two cases.

Work a small table

Use items A=(weight 2,value 3), B=(3,4), C=(4,5), capacity 5. With only A available, capacities 0 and 1 have value 0; capacities 2 through 5 have value 3. Adding B gives row [0,0,3,4,4,7]. At capacity 5, including B adds its value 4 to D[1,2]=3. Adding C gives [0,0,3,4,5,7]. The final answer is 7, achieved by A and B.

To reconstruct, begin at (i=3,c=5). Since D[3,5]=D[2,5], choose to omit C under a documented tie policy. At (2,5), including B explains the improvement, so record B and reduce capacity to 2. At (1,2), record A. Reverse the recovered list if output order matters, and independently verify total weight 5 and value 7.

Space optimization changes reconstruction

Only the previous row is needed for the value calculation, so one can use O(W) memory. A one-dimensional zero-one update must process capacities downward; an upward scan can reuse the same item’s newly updated state and accidentally solve the unbounded version. Reconstructing a selection after discarding rows requires additional decision information, recomputation, or another method. Value-only and witness-producing interfaces have different memory requirements.

The O(nW) running time is pseudo-polynomial: W is a numeric value, while its binary encoding uses only O(log W) bits. This distinction matters when someone claims the algorithm makes knapsack generally easy. It is effective when the capacity scale is moderate, not an unrestricted polynomial-time solution in input bit length.

MIT’s dynamic-programming lectures emphasize state, recurrence, base cases, order, and reconstruction. Apply those five questions before coding. Then test empty input, zero capacity, items too heavy to fit, and ties between several optimal selections.

Practice problem

Use items A=(2,3), B=(3,4), C=(4,6) and capacity 6. Build all rows D[i,c] for c=0…6, reconstruct an optimum, and verify its weight and value. Then explain concretely how an upward one-dimensional update for the single item A and capacity 4 would incorrectly reuse A.

Worked solution

The initial row is [0,0,0,0,0,0,0]. After A: [0,0,3,3,3,3,3]. After B: [0,0,3,4,4,7,7]. After C: [0,0,3,4,6,7,9]. At capacity 6, choose C and then A, with weight 4+2=6 and value 6+3=9. In an upward scan for A, capacity 2 becomes 3; when capacity 4 is processed later, it reads that newly updated capacity 2 and obtains 6, as if A could be selected twice. Downward iteration reads only states from before the current item was incorporated, preserving the zero-one constraint.

Check your understanding

A zero-one knapsack starts with zero values. Its only item weighs 2 and is worth 3. Updating capacities upward in place gives value 6 at capacity 4. What went wrong?

• The algorithm used the same item twice through an already updated state.
• The capacity must always be prime.
• The value is correct for zero-one knapsack.
• The initial state should assign value 3 at capacity 0.

Explanation

The capacity 4 update reads the new capacity 2 value, which already includes the current item. Downward updates retain the previous-item state.

Capacity W is encoded with b bits and may be about 2^b. How should an O(nW) dynamic program be described in terms of input length?

• O(n log b) because the capacity is written in binary.
• Always O(nb).
• Independent of b because W is one input field.
• Potentially O(n2^b), so the numeric-capacity bound is pseudo-polynomial.

Explanation

The number of table entries depends on the magnitude W, while writing W requires only logarithmically many bits.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →