View source for Knapsack problem

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 20 formulas, 20 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
Given a knapsack (container) of total capacity $c$, and $n$ objects with weights $a_1 , \dots , a _ { n }$ and respective values $c_ 1 , \ldots , c _ { n }$, the problem is to pack as much value in the knapsack as possible.

Abstractly the problem can be formulated as follows. Given positive integers $c$, $a_1 , \dots , a _ { n }$, $c_ 1 , \ldots , c _ { n }$, the problem is to maximize $\sum  c_ { i } x _ { i }$ subject to $\sum _ { i } a _ { i } x _ { i } \leq c$ and $x _ { i } \in \{ 0,1 \}$.

The [[Greedy algorithm|greedy algorithm]] to  "solve"  this proceeds as follows. It is natural to favour objects with the greatest value/weight density. So, relabel, if needed, the objects so that $ c  _ { 1 } / a  _ { 1 } \geq \ldots \geq c  _ { n } / a  _ { n }$. Then select $x _ { 1 } , \ldots , x _ { n }$ recursively according to

\begin{equation*} x _ { i } = \left\{ \begin{array} { l l } { 1 } &amp; { \text { if } a _ { i } \leq c - \sum _ { j = 1 } ^ { i - 1 } a _ { j } x _ { j }, } \\ { 0 } &amp; { \text { otherwise. } } \end{array} \right. \end{equation*}

This greedy algorithm has a performance ratio of $2$, i.e. it is guaranteed to find a solution which is within a factor $2$ of the optimal one.

If the $x_{i}$ are allowed to take fractional values (i.e. values in $[ 0,1 ]$ instead of $\{ 0,1 \}$), then the greedy algorithm is optimal.

The knapsack problem is $\cal N P$-hard, cf. [[NP|$\cal N P$]].

====References====
<table><tr><td valign="top">[a1]</td> <td valign="top">  "Encyclopedia of Operations Research and Management Science"  S.I. Gass (ed.)  C.M. Harris (ed.) , Kluwer Acad. Publ.  (1996)  pp. 325–326</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  M. Grötschel,   L. Lovász,   "Combinatorial optimization"  R.L. Graham (ed.)  M. Grötschel (ed.)  L. Lovász (ed.) , ''Handbook of Combinatorics'' , Elsevier  (1995)  pp. 1541–1579</td></tr></table>