Editing Knapsack problem (section)

== Variations ==
{{Main|List of knapsack problems}}

There are many variations of the knapsack problem that have arisen from the vast number of applications of the basic problem. The main variations occur by changing the number of some problem parameter such as the number of items, number of objectives, or even the number of knapsacks.

===Multi-dimensional objective===
Here, instead of a single objective (e.g. maximizing the monetary profit from the items in the knapsack), there can be several objectives. For example, there could be environmental or social concerns as well as economic goals. Problems frequently addressed include portfolio and transportation logistics optimizations.<ref>Chang, T. J., et al. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.6698&rep=rep1&type=pdf Heuristics for Cardinality Constrained Portfolio Optimization].
Technical Report, London SW7 2AZ, England: The Management School, Imperial
College, May 1998</ref><ref>Chang, C. S., et al. "[https://scholarbank.nus.edu.sg/handle/10635/72660 Genetic Algorithm Based Bicriterion Optimization for Traction Substations in DC Railway System]." In Fogel [102], 11-16.</ref>

As an example, suppose you run a cruise ship. You have to decide how many famous comedians to hire. This boat can handle no more than one ton of passengers and the entertainers must weigh less than 1000&nbsp;lbs. Each comedian has a weight, brings in business based on their popularity and asks for a specific salary. In this example, you have multiple objectives. You want, of course, to maximize the popularity of your entertainers while minimizing their salaries. Also, you want to have as many entertainers as possible.

===Multi-dimensional weight===
Here, the weight of knapsack item <math>i</math> is given by a D-dimensional vector <math>\overline{w_i}=(w_{i1},\ldots,w_{iD})</math> and the knapsack has a D-dimensional capacity vector <math>(W_1,\ldots,W_D)</math>. The target is to maximize the sum of the values of the items in the knapsack so that the sum of weights in each dimension <math>d</math> does not exceed <math>W_d</math>.

Multi-dimensional knapsack is computationally harder than knapsack; even for <math>D=2</math>, the problem does not have [[EPTAS]] unless P<math>=</math>NP.<ref>{{cite journal | last1 = Kulik | first1 = A. | last2 = Shachnai | first2 = H. | author2-link = Hadas Shachnai | year = 2010 | title = There is no EPTAS for two dimensional knapsack | url = https://www.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf| journal = Inf. Process. Lett. | volume = 110 | issue = 16| pages = 707–712 | doi=10.1016/j.ipl.2010.05.031| citeseerx = 10.1.1.161.5838 }}</ref> However, the algorithm in<ref name=CohenGrebla>Cohen, R. and Grebla, G. 2014. [http://wimnet.ee.columbia.edu/wp-content/uploads/2013/03/paper_short.pdf "Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes"]. in ''Proc. IEEE INFOCOM'14'', 2427–2435.</ref> is shown to solve sparse instances efficiently. An instance of multi-dimensional knapsack is sparse if there is a set <math>J=\{1,2,\ldots,m\}</math> for <math>m<D</math> such that for every knapsack item <math>i</math>, <math> \exists z>m</math> such that <math>\forall j\in J\cup \{z\},\ w_{ij}\geq 0</math> and <math>\forall y\notin J\cup\{z\}, w_{iy}=0</math>. Such instances occur, for example, when scheduling packets in a wireless network with relay nodes.<ref name=CohenGrebla/> The algorithm from<ref name=CohenGrebla/> also solves sparse instances of the multiple choice variant, multiple-choice multi-dimensional knapsack.

The IHS (Increasing Height Shelf) algorithm is optimal for 2D knapsack (packing squares into a two-dimensional unit size square): when there are at most five squares in an optimal packing.<ref>Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [https://scholar.google.com/citations?user=txyI5aAAAAAJ]: ''2D knapsack: Packing squares'', Theoretical Computer Science Vol. 508, pp. 35–40.</ref>

===Multiple knapsacks===
{{Main|Multiple knapsack problem}}
Here, there are multiple knapsacks. This may seem like a trivial change, but it is not equivalent to adding to the capacity of the initial knapsack, as each knapsack has its own capacity constraint. This variation is used in many loading and scheduling problems in Operations Research and has a [[Polynomial-time approximation scheme]].<ref>{{Cite journal |last=Chandra Chekuri and Sanjeev Khanna |date=2005 |title=A PTAS for the multiple knapsack problem |journal=SIAM Journal on Computing |volume=35 |issue=3 |pages=713–728 |citeseerx=10.1.1.226.3387 |doi=10.1137/s0097539700382820}}</ref>   This variation is similar to the [[Bin packing problem|Bin Packing Problem]]. It differs from the Bin Packing Problem in that a subset of items can be selected, whereas, in the Bin Packing Problem, all items have to be packed to certain bins. 

===Quadratic===
{{Main|Quadratic knapsack problem}}
The '''quadratic knapsack problem''' maximizes a quadratic objective function subject to binary and linear capacity constraints.<ref name="QKP">{{cite journal | title = Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems |author1=Wu, Z. Y. |author2=Yang, Y. J. |author3=Bai, F. S. |author4=Mammadov, M. | journal = J Optim Theory Appl | year = 2011 | volume = 151 |issue=2 | pages = 241&ndash;259 | doi = 10.1007/s10957-011-9885-4 |s2cid=31208118 }}</ref> The problem was introduced by Gallo, Hammer, and Simeone  in 1980,<ref>{{cite book | chapter = Quadratic knapsack problems |author1=Gallo, G. |author2=Hammer, P. L. |author3=Simeone, B. | title = Combinatorial Optimization |series= Mathematical Programming Studies | year = 1980 | volume = 12 | pages = 132&ndash;149 | doi = 10.1007/BFb0120892 |isbn=978-3-642-00801-6 }}</ref> however the first treatment of the problem dates back to Witzgall in 1975.<ref>{{cite journal | title = Mathematical methods of site selection for Electronic Message Systems (EMS) | author = Witzgall, C. | journal = NASA Sti/Recon Technical Report N | publisher = NBS Internal report | year = 1975| volume = 76 | page = 18321 | bibcode = 1975STIN...7618321W }}</ref>

=== Geometric ===
In the '''geometric knapsack problem''', there is a set of rectangles with different values, and a rectangular knapsack. The goal is to pack the largest possible value into the knapsack.<ref>{{Cite journal|last1=Galvez|first1=Waldo|last2=Grandoni|first2=Fabrizio|last3=Ingala|first3=Salvatore|last4=Heydrich|first4=Sandy|last5=Khan|first5=Arindam|last6=Wiese|first6=Andreas|date=2021|title=Approximating Geometric Knapsack via L-packings|url=https://doi.org/10.1145/3473713|pages=33:1–33:67|doi=10.1145/3473713|journal = ACM Trans. Algorithms|volume=17 |issue=4 |arxiv=1711.07710}}</ref>

=== Online ===
In the '''online knapsack problem''', the items come one by one. Whenever an item arrives, we must decide immediately whether to put it in the knapsack or discard it. There are two variants: (a) non-removable - an inserted item remains in the knapsack forever; (b) removable - an inserted item may be removed later, to make room for a new item.

Han, Kawase and Makino<ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |date=2015-01-11 |title=Randomized algorithms for online knapsack problems |url=https://www.sciencedirect.com/science/article/pii/S0304397514007798 |journal=Theoretical Computer Science |volume=562 |pages=395–405 |doi=10.1016/j.tcs.2014.10.017 |issn=0304-3975}}</ref> present a randomized algorithm for the unweighted non-removable setting. It is 2-competitive, which is the best possible. For the weighted removable setting, they give a 2-competitive algorithm, prove a lower bound of ~1.368 for randomized algorithms, and prove that no deterministic algorithm can have a constant competitive ratio. For the unweighted removable setting, they give an 10/7-competitive-ratio algorithm, and prove a lower  bound of 1.25. 

There are several other papers on the online knapsack problem.<ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |date=2014-09-01 |title=Online Unweighted Knapsack Problem with Removal Cost |url=https://link.springer.com/article/10.1007/s00453-013-9822-z |journal=Algorithmica |language=en |volume=70 |issue=1 |pages=76–91 |doi=10.1007/s00453-013-9822-z |issn=1432-0541}}</ref><ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |last4=Guo |first4=He |date=2014-06-26 |title=Online removable knapsack problem under convex function |journal=Theoretical Computer Science |series=Combinatorial Optimization: Theory of algorithms and Complexity |volume=540-541 |pages=62–69 |doi=10.1016/j.tcs.2013.09.013 |issn=0304-3975|doi-access=free }}</ref><ref>{{Citation |last1=Han |first1=Xin |title=Online Knapsack Problems with a Resource Buffer |date=2019-09-22 |arxiv=1909.10016 |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |last4=Yokomaku |first4=Haruki}}</ref>