The Knapsack Problem

A PIP model with a single constraint is known as a knapsack problem. Such a problem can take the form

Maximize

P$1$Y$1+$ P$2$Y$2+$

$...$

$+$PnYn

subject to

a$121+$ a$222+$

$+$ anyn$<=$b$,$

$(9\mathrm{.}127)$

where $1,2,...,$ Yn $>=0$ and take integer values.

The name 'knapsack' arises from the rather contrived application of a hiker trying to fill her knapsack to maximum total value. Each item she considers taking with her has a certain value and a certain weight. An overall weight limitation gives the single constraint.