Editing Knapsack problem (section)

== Definition ==
The most common problem being solved is the '''0-1 knapsack problem''', which restricts the number ''<math>x_i</math>'' of copies of each kind of item to zero or one. Given a set of ''<math>n</math>'' items numbered from 1 up to ''<math>n</math>'', each with a weight ''<math>w_i</math>'' and a value ''<math>v_i</math>'', along with a maximum weight capacity ''<math>W</math>'',
: maximize <math>\sum_{i=1}^n v_i x_i</math>
: subject to <math>\sum_{i=1}^n w_i x_i \leq W</math> and <math>x_i \in \{0,1\}</math>.
Here ''<math>x_i</math>'' represents the number of instances of item ''<math>i</math>'' to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity.

The '''bounded knapsack problem''' ('''BKP''') removes the restriction that there is only one of each item, but restricts the number <math>x_i</math> of copies of each kind of item to a maximum non-negative integer value <math>c</math>:
: maximize <math>\sum_{i=1}^n v_i x_i</math>
: subject to <math>\sum_{i=1}^n w_i x_i \leq W</math> and <math>x_i \in \{0,1,2,\dots,c\}.</math>

The '''unbounded knapsack problem''' ('''UKP''') places no upper bound on the number of copies of each kind of item and can be formulated as above except that the only restriction on <math>x_i</math> is that it is a non-negative integer.
: maximize <math>\sum_{i=1}^n v_i x_i</math>
: subject to <math>\sum_{i=1}^n w_i x_i \leq W</math> and <math>x_i \in \mathbb{N}.</math>

One example of the unbounded knapsack problem is given using the figure shown at the beginning of this article and the text "if any number of each book is available" in the caption of that figure.