= Solution
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 \i[at most] $c$. Then
$$
\boxed{K(c)=\max\bigl(\{0\}\cup\{v_i+K(c-w_i):1\le i\le n,\ w_i\le c\}\bigr),\quad K(0)=0.}
$$
The 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.
Back to article page
