# Knapsack problem

An integer program of the form,

$LaTeX: \max \{c^Tx : x \in \mathbb{Z}^n, \, x \ge 0,\, \mbox{ and } a^Tx \le b \},$

where $LaTeX: a > 0$. The original problem models the maximum value of a knapsack that is limited by volume or weight $LaTeX: (b)$, where $LaTeX: x_j$ is the number of items of type $LaTeX: j$ put into the knapsack at unit return $LaTeX: c_j$, that uses $LaTeX: a_j$ units per item.

The group knapsack problem has this form, except that it pertains to Gomory's corner polyhedron problem for general integer programming.

The multi-dimensional knapsack problem has more constraints (e.g., volume and weight), $LaTeX: Ax <= b$, where $LaTeX: A >= 0$ with $LaTeX: Ae > 0$ and $LaTeX: e^TA > 0$.