Bounded Knapsack Problems
Why
We consider the knapsack problem in which the $n$ items are considered to be types of items and we have a certain quantity of each.
Definition
Suppose we have zero-one knapsack problem data
$(p, w, c)$ where $p: [n] \to \R $ is the
profit function, $w: [n] \to \R _+$ is the
weight function, and $c \in \R _+$ is the
capacity constraint.
Given budgets $b_1,
\dots , b_n \in \Z _+$, find $x \in \Z _+^n$ to
\[
\begin{aligned}
\text{minimize } & \quad \sum_i p_ix_i \\
\text{subject to } & \quad \sum_i w_ix_i \leq c \\
& \quad 0 \leq x_i \leq b_i, \quad i = 1, \dots , n, \\
&\quad x_i \in \Z \quad i = 1, \dots , n
\end{aligned}
\]