# 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} δ_{i}w_{i} ≤ c, and the total value, ∑_{i=1}^{N} δ_{i}v_{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

Steven Skiena's Stony Brook Algorithm Repository (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 26 July 2021.

HTML page formatted Mon Jul 26 11:58:06 2021.

Cite this as:

Paul E. Black, "knapsack problem", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 26 July 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/knapsackProblem.html