NIST

knapsack problem

(classic problem)

Definition: Given items of different values and volumes, find the most valuable set of items that fit in a knapsack of fixed volume.

Formal Definition: There is a knapsack of capacity c > 0 and N items. Each item has value vi > 0 and weight wi > 0. Find the selection of items (δi = 1 if selected, 0 if not) that fit, ∑i=1N δiwi ≤ c, and the total value, ∑i=1N δivi, is maximized.

Also known as 0-1 knapsack problem, binary knapsack problem.

See also fractional knapsack problem, unbounded knapsack problem, bin packing problem, cutting stock problem, NP-complete.

Note: Also called 0-1 or binary knapsack (each item may be taken (1) or not (0)), in contrast to the fractional knapsack problem. Also called bounded knapsack (BKP) because there are a limited number of items, in contrast to the unbounded knapsack problem. The decision problem is, given items of different values and volumes and a knapsack, is there a subset that exceeds a certain value? The decision problem is NP-complete.

Author: PEB

Implementation

(Fortran and Pascal). GAMS Class G2c3 (Fortran).

More information


From xkcd by Creative Commons Attribution-NonCommercial 2.5 License.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 22 April 2015.
HTML page formatted Mon May 18 09:42:24 2015.

Cite this as:
Paul E. Black, "knapsack problem", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 22 April 2015. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/knapsackProblem.html