Namespaces
Variants
Actions

Difference between revisions of "Knapsack problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 20 formulas out of 20 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
Given a knapsack (container) of total capacity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300401.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300402.png" /> objects with weights <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300403.png" /> and respective values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300404.png" />, the problem is to pack as much value in the knapsack as possible.
+
<!--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.
  
Abstractly the problem can be formulated as follows. Given positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300405.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300406.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300407.png" />, the problem is to maximize <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300408.png" /> subject to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k1300409.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004010.png" />.
+
Out of 20 formulas, 20 were replaced by TEX code.-->
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004011.png" />. Then select <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004012.png" /> recursively according to
+
{{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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004013.png" /></td> </tr></table>
+
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 \}$.
  
This greedy algorithm has a performance ratio of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004014.png" />, i.e. it is guaranteed to find a solution which is within a factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004015.png" /> of the optimal one.
+
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
  
If the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004016.png" /> are allowed to take fractional values (i.e. values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004017.png" /> instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004018.png" />), then the greedy algorithm is optimal.
+
\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*}
  
The knapsack problem is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004019.png" />-hard, cf. [[NP|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k130/k130040/k13004020.png" />]].
+
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====
 
====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>
+
<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>

Latest revision as of 15:30, 1 July 2020

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
How to Cite This Entry:
Knapsack problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Knapsack_problem&oldid=49904
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article