Knapsack problem

From Encyclopedia of Mathematics
Revision as of 17:17, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Given a knapsack (container) of total capacity , and objects with weights and respective values , the problem is to pack as much value in the knapsack as possible.

Abstractly the problem can be formulated as follows. Given positive integers , , , the problem is to maximize subject to and .

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 . Then select recursively according to

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

If the are allowed to take fractional values (i.e. values in instead of ), then the greedy algorithm is optimal.

The knapsack problem is -hard, cf. .


[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:
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article