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.
From xkcd by Creative Commons Attribution-NonCommercial 2.5 License.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 8 November 2010.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "knapsack problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 8 November 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/knapsackProblem.html