The knapsack problem is the following problem in combinatorial optimization:
Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.
Definition
0-1 knapsack problem
The most common problem being solved is the 0-1 knapsack problem, which restricts the number \(x_{i}\) of copies of each kind of item to zero or one. Given a set of \(n\) items numbered from 1 up to \(n\), each with a weight \(w_{i}\) and a value \(v_{i}\), along with a maximum weight capacity \(W\),
maximize \(\sum _{i=1}^{n}v_{i}x_{i}\)
subject to \(\sum _{i=1}^{n}w_{i}x_{i}\leq W\) and \(x_{i}\in \{0,1\}\)
Here \(x_i\) represents the number of instances of item \(i\) to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack’s capacity.
Bounded knapsack problem
The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number \(x_{i}\) of copies of each kind of item to a maximum non-negative integer value \(c\)
Unbounded knapsack problem
The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except that the only restriction on \(x_{i}\) is that it is a non-negative integer.
Variations
The subset sum problem [Subset sum problem] is a special case of the decision and 0-1 problems where each kind of item, the weight equals the value: \(w_{i}=v_{i}\).