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 generalisations have been examined.

Common to all versions are a set of "n" items, with each item $1\; leq\; j\; leq\; n$ having an associated profit "p_j" and weight "w_j". 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:

If for each item the profits and weights are identical, we get the subset sum problem (often the corresponding decision problem is given instead):

Quadratic knapsack problem

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 "B_j" times, each "pattern" of items which fit into a single knapsack have a variable, "x_i" (there are "m" patterns), and pattern "i" uses item "j" "b_ij" 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:

Several other knapsack-like problems exists, although they are less common than the above. They include:

Collapsing knapsack problem

Nested knapsack problem

Nonlinear knapsack problem

Inverse-parametric knapsack problem

(References needed for the last four problems)----
* D. Pisinger, [http://www.diku.dk/users/pisinger/95-1.pdf "Algorithms for Knapsack Problems"] , Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).

* cite book
authorlink = Hans | Kellerer
first = Hans | Kellerer
coauthors = U. Pferschy D. Pisinger
year = 2005
title = Knapsack Problems
publisher = Springer Verlag
id = ISBN 3-540-40286-1