= Solution
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. Then
$$
\boxed{D(0,c)=0,\qquad D(i,c)=\begin{cases}
D(i-1,c),&w_i>c,\\
\max\{D(i-1,c),\ v_i+D(i-1,c-w_i)\},&w_i\le c.
\end{cases}}
$$
The 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.
Back to article page
