List of Knapsack Problems - Direct Generalizations

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 u_j (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, and exactly one item must be taken from each class, we get the multiple-choice knapsack problem:

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, 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 (on page 423) 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.