Theknapsack problem is one of the most studied problems incombinatorial optimization, with many real-life applications. For this reason, many special cases and generalizations have been examined.^[1][2]

Common to all versions are a set ofn items, with each item${\displaystyle 1\le j\le n}$ having an associated profitp_j and weightw_j. The binary decision variablex_j 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 exceedW. Generally, these coefficients are scaled to become integers, and they are almost always assumed to be positive.

Theknapsack problem in its most basic form:

maximize${\displaystyle \sum _{j=1}^n{p}_j{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_j\le W,}$
	${\displaystyle x_j\in \{0,1\}}$	${\displaystyle \mathrm{\forall }j\in \{1,\dots ,n\}}$

One common variant is that each item can be chosen multiple times. Thebounded knapsack problem specifies, for each itemj, an upper boundu_j (which may be a positive integer, or infinity) on the number of times itemj can be selected:

maximize${\displaystyle \sum _{j=1}^n{p}_j{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_j\le W,}$
	${\displaystyle 0\le x_j\le u_j,x_j}$ integral for allj

Theunbounded knapsack problem (sometimes called theinteger knapsack problem) does not put any upper bounds on the number of times an item may be selected:

maximize${\displaystyle \sum _{j=1}^n{p}_j{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_j\le W,}$
	${\displaystyle x_j\ge 0,x_j}$ integral for allj

The unbounded variant was shown to beNP-complete in 1975 by Lueker.^[3] Both the bounded and unbounded variants admit anFPTAS (essentially the same as the one used in the 0-1 knapsack problem).

If the items are subdivided intok classes denoted${\displaystyle N_i}$, and exactly one item must be taken from each class, we get themultiple-choice knapsack problem:

maximize${\displaystyle \sum _{i=1}^k\sum _{j\in N_i}{p}_{ij}{x}_{ij}}$
subject to	${\displaystyle \sum _{i=1}^k\sum _{j\in N_i}{w}_{ij}{x}_{ij}\le W,}$
	${\displaystyle \sum _{j\in N_i}{x}_{ij}=1,}$	for all${\displaystyle 1\le i\le k}$
	${\displaystyle x_{ij}\in \{0,1\}}$	for all${\displaystyle 1\le i\le k}$ and all${\displaystyle j\in N_i}$

If for each item the profit and weight are equal, we get thesubset sum problem (often the correspondingdecision problem is given instead):

maximize${\displaystyle \sum _{j=1}^n{p}_j{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{p}_j{x}_j\le W,}$
	${\displaystyle x_j\in \{0,1\}}$

If we haven items andm knapsacks with capacities${\displaystyle W_i}$, we get themultiple knapsack problem:

maximize${\displaystyle \sum _{i=1}^m\sum _{j=1}^n{p}_j{x}_{ij}}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_{ij}\le W_i,}$	for all${\displaystyle 1\le i\le m}$
	${\displaystyle \sum _{i=1}^m{x}_{ij}\le 1,}$	for all${\displaystyle 1\le j\le n}$
	${\displaystyle x_{ij}\in \{0,1\}}$	for all${\displaystyle 1\le j\le n}$ and all${\displaystyle 1\le i\le m}$

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 havemultiple subset sum problem.

Quadratic knapsack problem:

maximize${\displaystyle \sum _{j=1}^n{p}_j{x}_j+\sum _{i=1}^{n-1}\sum _{j=i+1}^n{p}_{ij}{x}_i{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_j\le W,}$
	${\displaystyle x_j\in \{0,1\}}$	for all${\displaystyle 1\le j\le n}$

Set-Union Knapsack Problem:

SUKP is defined by Kellerer et al^[2] (on page 423) as follows:

Given a set of${\displaystyle n}$ items${\displaystyle N=\{1,\dots ,n\}}$ and a set of${\displaystyle m}$ so-called elements${\displaystyle P=\{1,\dots ,m\}}$, each item${\displaystyle j}$ corresponds to a subset${\displaystyle P_j}$ of the element set${\displaystyle P}$. The items${\displaystyle j}$ have non-negative profits${\displaystyle p_j}$,${\displaystyle j=1,\dots ,n}$, and the elements${\displaystyle i}$ have non-negative weights${\displaystyle w_i}$,${\displaystyle i=1,\dots ,m}$. 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.

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 themultiple-constrained knapsack problem,multidimensional knapsack problem, orm-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.

maximize${\displaystyle \sum _{j=1}^n{p}_j{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{w}_{ij}{x}_j\le W_i,}$	for all${\displaystyle 1\le i\le m}$
	${\displaystyle x_j\ge 0}$,${\displaystyle x_j}$ integer	for all${\displaystyle 1\le j\le n}$

The 0-1 variant (for any fixed${\displaystyle m\ge 2}$) was shown to beNP-complete around 1980 and more strongly, has no FPTAS unless P=NP.^[4][5]

The bounded and unbounded variants (for any fixed${\displaystyle m\ge 2}$) also exhibit the same hardness.^[6]

For any fixed${\displaystyle m\ge 2}$, these problems do admit apseudo-polynomial time algorithm (similar to the one for basic knapsack) and aPTAS.^[2]

If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:

maximize${\displaystyle \sum _{j=1}^n{x}_j}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_j\le W,}$
	${\displaystyle x_j\in \{0,1\},}$	${\displaystyle \mathrm{\forall }j\in \{1,\dots ,n\}}$

If we have a number of containers (of the same size), and we wish to pack alln items in as few containers as possible, we get thebin packing problem, which is modelled by having indicator variables${\displaystyle y_i=1\iff }$ containeri is being used:

minimize${\displaystyle \sum _{i=1}^n{y}_i}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_{ij}\le W{y}_i,}$	${\displaystyle \mathrm{\forall }i\in \{1,\dots ,n\}}$
	${\displaystyle \sum _{i=1}^n{x}_{ij}=1}$	${\displaystyle \mathrm{\forall }j\in \{1,\dots ,n\}}$
	${\displaystyle y_i\in \{0,1\}}$	${\displaystyle \mathrm{\forall }i\in \{1,\dots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\}}$	${\displaystyle \mathrm{\forall }i\in \{1,\dots ,n\}\wedge \mathrm{\forall }j\in \{1,\dots ,n\}}$

Thecutting stock problem is identical to thebin packing problem, but since practical instances usually have far fewer types of items, another formulation is often used. Itemj is neededB_j times, each "pattern" of items which fit into a single knapsack have a variable,x_i (there arem patterns), and patterni uses itemjb_ij times:

minimize${\displaystyle \sum _{i=1}^m{x}_i}$
subject to	${\displaystyle \sum _{i=1}^m{b}_{ij}{x}_i\ge B_j,}$	for all${\displaystyle 1\le j\le n}$
	${\displaystyle x_i\in \{0,1,\dots ,n\}}$	for all${\displaystyle 1\le i\le m}$

If, to the multiple choice knapsack problem, we add the constraint that each subset is of sizen and remove the restriction on total weight, we get theassignment problem, which is also the problem of finding a maximalbipartite matching:

maximize${\displaystyle \sum _{i=1}^k\sum _{j=1}^n{p}_{ij}{x}_{ij}}$
subject to	${\displaystyle \sum _{i=1}^n{x}_{ij}=1,}$	for all${\displaystyle 1\le j\le n}$
	${\displaystyle \sum _{j=1}^n{x}_{ij}=1,}$	for all${\displaystyle 1\le i\le n}$
	${\displaystyle x_{ij}\in \{0,1\}}$	for all${\displaystyle 1\le i\le k}$ and all${\displaystyle j\in N_i}$

In theMaximum Density Knapsack variant there is an initial weight${\displaystyle w_0}$, and we maximize the density of selected items which do not violate the capacity constraint:^[7]

maximize${\displaystyle \frac{\sum _{j=1}^n{x}_j{p}_j}{w_0+\sum _{j=1}^n{x}_j{w}_j}}$
subject to	${\displaystyle \sum _{j=1}^n{w}_j{x}_j\le W,}$
	${\displaystyle x_j\in \{0,1\},}$	${\displaystyle \mathrm{\forall }j\in \{1,\dots ,n\}}$

Although less common than those above, several other knapsack-like problems exist, including:

• Nested knapsack problem
• Collapsing knapsack problem
• Nonlinear knapsack problem
• Inverse-parametric knapsack problem

The last three of these are discussed in Kellerer et al's reference work,Knapsack Problems.^[2]

• "Algorithms for Knapsack Problems", D. Pisinger. Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).

• Combinatorial optimization

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata