= Unbounded knapsack problem
= Unbounded knapsack
{synonym}
In the <unbounded knapsack problem>, each item type may be used any <nonnegative integer> number of times. With <positive integer> weights $w_i$, values $v_i$ and capacity $W$, maximize $\sum_i v_ix_i$ subject to $\sum_iw_ix_i\leq W$ and $x_i\in\mathbb Z_{\geq0}$.
A <dynamic programming> recurrence for capacity-at-most value is $F(c)=\max(0,\max_{w_i\leq c}(v_i+F(c-w_i)))$. Evaluate capacities in increasing order so repeated uses are available. With weights three and five, values four and seven, and capacity ten, two weight-five items give value fourteen. A zero-weight positive-value item would make the objective unbounded, explaining the positive-weight hypothesis.
Back to article page
