Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 6

Use positive integral item weights and a nonnegative integral capacity. For the unbounded knapsack problem, define $K(c)$ to be the best value with total weight at most $c$. ThenThe zero candidate is the empty selection, so unused capacity is allowed and an empty set of fitting items causes no problem. Every nonempty feasible selection has some last item $i$; removing one copy leaves a feasible solution at capacity $c-w_i$. Its value is bounded by the corresponding candidate. Conversely, taking an optimal smaller selection and adding that item attains the candidate, proving the recurrence relation by optimal substructure. Positive weights make every dependency strictly smaller.

Fill capacities in increasing order. There are $W+1$ entries, each scanning $n$ items, so the dynamic programming takes $O(nW)$ time and $O(W)$ storage. A winning item pointer at each capacity reconstructs the chosen multiplicities. These are capacity-dependent, pseudopolynomial bounds. For zero-weight items, any positive value makes the repetition problem unbounded; nonpositive-value zero-weight items may simply be discarded before using the recurrence.

Capacity alone cannot say which items have already been used. For the 0-1 knapsack problem, let $D(i,c)$ use only the first $i$ items, each at most once. ThenThe two alternatives omit item $i$ or take it. In the latter case its remaining companions must solve the smaller problem using the first $i-1$ items; otherwise replacing them would improve the whole selection. Both branches reduce the item index, so taking item $i$ cannot take it again. This establishes the recurrence relation and optimal substructure.

Fill rows in increasing $i$ and return $D(n,W)$. There are $O(nW)$ entries with constant work each. Store the decisions for reconstruction; value-only computation uses $O(W)$ space by keeping two rows, or by scanning capacities downwards in a single row. A forward scan in a single row would instead allow repetitions. Nonnegative integral weights suffice for this version, including zero-weight items, because the item index always decreases.

This version of Kadane's algorithm, named for Joseph Born Kadane, permits the empty subsequence. For $j\ge 1$, let $E_j$ be the maximum of zero and the weight of a contiguous subsequence ending exactly at position $j$. Let $B_j$ be the best weight anywhere in the first $j$ positions. UseA segment ending at $j$ either extends one ending at $j-1$ or starts at $j$; the zero candidate permits discarding a negative predecessor and the empty answer. Any best segment of the first $j$ positions either ends at $j$ or already occurs in the first $j-1$. These two decompositions prove the dynamic programming equations by induction.

Here is an implementation returning endpoints, using zero-based indexing:There is exactly one addition per input element, hence $n$ additions and $O(n)$ comparisons. Auxiliary storage is $O(1)$. The all-negative case retains interval $[0,0)$ and weight zero. The example returns $[3,6)$ and weight 8, hence the desired contiguous subsequence.