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 287 by Randall Munroe. 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 19 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "knapsack problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 19 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/knapsackProblem.html