= Solution
For the <unbounded knapsack problem>, let $F(c)$ be the greatest total value obtainable with weight at most capacity $c$. Assume positive integer item weights and nonnegative integer capacity $W$. Set $F(0)=0$, and fill increasing capacities using
$$
F(c)=\max\bigl(\{0\}\cup\{v_i+F(c-w_i):w_i\leq c\}\bigr).
$$
The zero alternative permits unused capacity. If a nonempty optimum includes item $i$, removing one copy leaves a feasible smaller-capacity instance; its remaining value cannot exceed $F(c-w_i)$. Conversely every candidate in the displayed maximum is feasible, proving equality. The smaller-capacity state allows the same type again, implementing repetition.
The answer is \b[$F(W)$, computed in $O(nW)$ time and $O(W)$ space]. Record an attaining item at each state to reconstruct the multiset. This is <pseudopolynomial time>, because $W$ is a number whose binary representation may have only $O(\log W)$ bits. A positive-value zero-weight type would make the optimum unbounded and must be excluded or detected separately.
Back to article page
