= Bounded knapsack problem
The <bounded knapsack problem> adds per-type upper <limits> $0\leq x_i\leq b_i$ to the integer <knapsack problem>. It interpolates between <0-1 knapsack problem> ($b_i=1$) and the <unbounded knapsack problem>.
Processing types one at a time gives $F_i(c)=\max_{0\leq k\leq b_i,\,kw_i\leq c}(kv_i+F_{i-1}(c-kw_i))$. The previous-type index prevents the recurrence from exceeding the allowed count. For large $b_i$, splitting counts into power-of-two bundles and a final remainder reduces the bounded type to logarithmically many <0-1 knapsack problem> items while preserving every allowable count.
Back to article page
