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 ${\displaystyle 1\leq j\leq n}$ having an associated profit p_j ,weight w_j. The binary decision variable x_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 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:

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 ${\displaystyle N_{i}}$, and exactly one item must be taken from each class, we get the multiple-choice knapsack problem:

...
Wikipedia