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 v_i > 0 and weight w_i > 0. Find the selection of items (δ_i = 1 if selected, 0 if not) that fit, ∑_i=1^N δ_iw_i ≤ c, and the total value, ∑_i=1^N δ_iv_i, 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

More information

From xkcd by Creative Commons Attribution-NonCommercial 2.5 License.

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