Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 7 / b / Solution

In the 0-1 knapsack problem, item $j$ has weight $w_j$ and value $v_j$. Choose a subset of the $n$ items, using each at most once, whose total weight is at most $W$ and whose total value is as large as possible. For the capacity-indexed dynamic program, take $W$ and the weights to be nonnegative integers. The empty choice is allowed.

Let $K[j,c]$ be the greatest value attainable using only items $1,\dots ,j$ with capacity $c$. The base case is $K[0,c]=0$. With item $j$ unavailable when it is too heavy, the recurrence isEvery feasible optimum either excludes item $j$, giving the first candidate, or includes it exactly once, leaving capacity $c-w_j$ for earlier items. The principle of optimality proves that the remaining earlier items must attain the indicated residual optimum. Conversely, either candidate constructs a feasible solution, so taking the larger is both necessary and sufficient. Mathematical induction on $j$ proves the table's meaning and the final answer $\boxed{K[n,W]}$.

Store item weights and values in arrays and the values in a two-dimensional array with $(n+1)(W+1)$ entries. Fill rows in increasing $j$; each entry uses at most two values from the previous row. There are $n(W+1)$ constant-work updates, givingFor positive growing capacities this is the familiar $\Theta (nW)$ bound. The $+1$ terms also cover capacity zero and zero-weight items: one must not initialize every $K[j,0]$ to zero if zero-weight, positive-value items are allowed.

To recover an actual subset, store the chosen alternative at each entry or compare the two candidates while tracing backward from $(n,W)$. A selected item changes $(j,c)$ to $(j-1,c-w_j)$; an excluded item changes it to $(j-1,c)$. This takes $O(n)$ extra time.

If only the optimal value is needed, keep two rows, using $\Theta (W+1)$ space. With strictly positive weights, a single capacity row updated in decreasing capacity also prevents item reuse. The two-row version handles zero weights without special in-place reasoning. The running time is pseudopolynomial, since the binary input length of $W$ is only logarithmic in its numerical value.