 Bounded knapsack problem

The bounded knapsack problem adds per-type upper limits $0\le x_i\le 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\le k\le b_i,k{w}_i\le c}(k{v}_i+F_{i-1}(c-k{w}_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.