Knapsack problem

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 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 } & { \text { if } a _ { i } \leq c - \sum _ { j = 1 } ^ { i - 1 } a _ { j } x _ { j }, } \\ { 0 } & { \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. $\cal N P$.

References

[a1]	"Encyclopedia of Operations Research and Management Science" S.I. Gass (ed.) C.M. Harris (ed.) , Kluwer Acad. Publ. (1996) pp. 325–326
[a2]	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