- List of knapsack problems
The
knapsack problem is one of the most studied problems incombinatorial 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 "pj" and weight "wj". 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 correspondingdecision problem is given instead):Quadratic knapsack problem The
cutting stock problem is identical to thebin 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 theassignment problem , which is also the problem of finding a maximalbipartite 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
Wikimedia Foundation. 2010.