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

Dynamic programming specifies a collection of overlapping subproblems, expresses each answer using smaller subproblem answers, and stores answers so each subproblem is solved once. One may fill a table in dependency order or use memoization to compute only requested entries. The key design choice is a state that retains every feature needed by later decisions.

The principle of optimality says that, after a decision in an optimal solution, the remaining decisions must solve the corresponding residual subproblem optimally. Otherwise, replacing that residual solution by a better one would improve the entire solution. This replacement argument requires the state to describe the residual constraints completely. Its useful form here isThe maximization applies to these value-maximization problems; minimization uses the analogous minimum recurrence.

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.

For the two-bag 0-1 knapsack problem, let $D[j,a,b]$ be the maximum total value using the first $j$ items, with remaining capacity limits $a$ in the first bag and $b$ in the second. Initialize $D[0,a,b]=0$. Item $j$ has exactly three possible decisions: omit it, place it in bag one if it fits, or place it in bag two if it fits. HenceA braced candidate with a false condition is omitted. All candidates refer to layer $j-1$, which prevents the same item from entering both bags. Combining two independently optimized single-bag knapsacks would not enforce that restriction.

The principle of optimality proves correctness exactly as in part (b): condition on the location of the final item and replace the earlier items by the optimal feasible residual assignment. Every candidate is realizable, and every feasible assignment belongs to one of the three cases. The final answer is $\boxed{D[n,W_1,W_2]}$.

Fill the three-dimensional array in increasing item index. Each of its $n(W_1+1)(W_2+1)$ updates inspects at most three candidates:For positive capacities the customary expression is $\Theta (n{W}_1{W}_2)$. Keeping only two item layers reduces space to $\Theta ((W_1+1)(W_2+1))$ for the optimal value. Full decision storage also permits backward reconstruction of each item's bag assignment. Nonnegative integer weights and capacities are the assumptions behind this capacity-indexed dynamic programming table.