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.

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.

Near the end, this page has drawings and a description of a knapsack.

Author: PEB

Implementation

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

Entry modified Wed Jan 26 08:55:31 2005.
HTML page formatted Wed Oct 26 09:47:41 2005.

Cite this as:
Paul E. Black, "knapsack problem", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/knapsackProblem.html