The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications. For this reason, many special cases and generalizations have been examined.
Contents
Common to all versions are a set of n items, with each item
The knapsack problem in its most basic form:
Direct generalizations
One common variant is that each item can be chosen multiple times. The bounded knapsack problem specifies, for each item j, an upper bound uj (which may be a positive integer, or infinity) on the number of times item j can be selected:
The unbounded knapsack problem (sometimes called the integer knapsack problem) does not put any upper bounds on the number of times an item may be selected:
The unbounded variant was shown to be NP-complete in 1975 by Lueker. Both the bounded and unbounded variants admit an FPTAS (essentially the same as the one used in the 0-1 knapsack problem).
If the items are subdivided into k classes denoted
If for each item the profits and weights are identical, we get the subset sum problem (often the corresponding decision problem is given instead):
If we have n items and m knapsacks with capacities
As a special case of the multiple knapsack problem, when the profits are equal to weights and all bins have the same capacity, we can have multiple subset sum problem.
Quadratic knapsack problem:
Set-Union Knapsack Problem:
SUKP is defined by Kellerer et al (on page 423) as follows:
Given a set of
Multiple constraints
If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply constrained knapsack problem, multidimensional knapsack problem, or m-dimensional knapsack problem. (Note, "dimension" here does not refer to the shape of any items.) This has 0-1, bounded, and unbounded variants; the unbounded one is shown below.
The 0-1 variant (for any fixed
The bounded and unbounded variants (for any fixed
For any fixed
Knapsack-like problems
If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:
If we have a number of containers (of the same size), and we wish to pack all n items in as few containers as possible, we get the bin packing problem, which is modelled by having indicator variables
The cutting stock problem is identical to the bin packing problem, but since practical instances usually have far fewer types of items, another formulation is often used. Item j is needed Bj times, each "pattern" of items which fit into a single knapsack have a variable, xi (there are m patterns), and pattern i uses item j bij times:
If, to the multiple choice knapsack problem, we add the constraint that each subset is of size n and remove the restriction on total weight, we get the assignment problem, which is also the problem of finding a maximal bipartite matching:
In the Maximum Density Knapsack variant there is an initial weight
Although less common than those above, several other knapsack-like problems exist, including:
The last three of these are discussed in Kellerer et al's reference work, Knapsack Problems.