List of knapsack problems


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.
Common to all versions are a set of n items, with each item having an associated profit pj,weight wj. The binary decision variable xj is used to select the item. The objective is to pick some of the items, with maximal total profit, while obeying that the maximum total weight of the chosen items must not exceed W. Generally, these coefficients are scaled to become integers, and they are almost always assumed to be positive.
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 on the number of times item j can be selected:
The unbounded 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.
If the items are subdivided into k classes denoted, and exactly one item must be taken from each class, we get the multiple-choice knapsack problem:
If for each item the profit and weight are equal, we get the subset sum problem :
If we have n items and m knapsacks with capacities, we get the multiple knapsack problem:
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 as follows:

Given a set of items and a set of so-called elements, each item corresponds to a subset of the element set. The items have non-negative profits,, and the elements have non-negative weights,. The total weight of a set of items is given by the total weight of the elements of the union of the corresponding element sets. The objective is to find a subset of the items with total weight not exceeding the knapsack capacity and maximal profit.

Multiple constraints

If there is more than one constraint, we get the multiply-constrained knapsack problem, multidimensional knapsack problem, or m-dimensional knapsack problem. This has 0-1, bounded, and unbounded variants; the unbounded one is shown below.
The 0-1 variant was shown to be NP-complete around 1980 and more strongly, has no FPTAS unless P=NP.
The bounded and unbounded variants also exhibit the same hardness.
For any fixed, these problems do admit a pseudo-polynomial time algorithm and a PTAS.

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, 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 container i is being used:
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, 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,
and we maximize the density of selected of items which do not violate the capacity constraint:
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.