Editing Knapsack problem (section)

=== Meet-in-the-middle ===
Another algorithm for 0-1 knapsack, discovered in 1974<ref>{{citation
 | last1 = Horowitz | first1 = Ellis
 | last2 = Sahni | first2 = Sartaj | author2-link = Sartaj Sahni
 | doi = 10.1145/321812.321823
 | journal = Journal of the Association for Computing Machinery
 | mr = 0354006
 | pages = 277–292
 | title = Computing partitions with applications to the knapsack problem
 | volume = 21
 | issue = 2
 | year = 1974| hdl = 1813/5989
 | s2cid = 16866858
 | hdl-access = free
 }}</ref> and sometimes called "meet-in-the-middle" due to parallels to [[Meet-in-the-middle attack|a similarly named algorithm in cryptography]], is exponential in the number of different items but may be preferable to the DP algorithm when <math>W</math> is large compared to ''n''. In particular, if the <math>w_i</math> are nonnegative but not integers, we could still use the dynamic programming algorithm by scaling and rounding (i.e. using [[fixed-point arithmetic]]), but if the problem requires <math>d</math> fractional digits of precision to arrive at the correct answer, <math>W</math> will need to be scaled by <math>10^d</math>, and the DP algorithm will require <math>O(W10^d)</math> space and <math>O(nW10^d)</math> time.

 '''algorithm''' Meet-in-the-middle '''is'''
     '''input:''' A set of items with weights and values.
     '''output:''' The greatest combined value of a subset.
 
     partition the set {1...''n''} into two sets ''A'' and ''B'' of approximately equal size
     compute the weights and values of all subsets of each set
 
     '''for each''' subset '''of''' ''A'' '''do'''
         find the subset of ''B'' of greatest value such that the combined weight is less than ''W''
 
     keep track of the greatest combined value seen so far

The algorithm takes <math>O(2^{n/2})</math> space, and efficient implementations of step 3 (for instance, sorting the subsets of B by weight, discarding subsets of B which weigh more than other subsets of B of greater or equal value, and using binary search to find the best match) result in a runtime of <math>O(n2^{n/2})</math>. As with the [[Meet-in-the-middle attack|meet in the middle attack]] in cryptography, this improves on the <math>O(n2^n)</math> runtime of a naive brute force approach (examining all subsets of <math>\{1...n\}</math>), at the cost of using exponential rather than constant space (see also [[baby-step giant-step]]). The current state of the art improvement to the meet-in-the-middle algorithm, using insights from Schroeppel and Shamir's Algorithm for Subset Sum, provides as a corollary a randomized algorithm for Knapsack which preserves the <math>O^{*}(2^{n/2})</math> (up to polynomial factors) running time and reduces the space requirements to <math>O^{*}(2^{0.249999n})</math> (see <ref>{{Cite arXiv |last1=Nederlof |first1=Jesper |last2=Węgrzycki |first2=Karol |date=2021-04-12 |title=Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors |class=cs.DS |eprint=2010.08576 }}</ref> Corollary 1.4). In contrast, the best known deterministic algorithm runs in <math>O^{*}(2^{n/2})</math> time with a slightly worse space complexity of <math>O^{*}(2^{n/4})</math>.<ref>{{Cite journal |last1=Schroeppel |first1=Richard |last2=Shamir |first2=Adi |date=August 1981 |title=A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems |url=http://epubs.siam.org/doi/10.1137/0210033 |journal=SIAM Journal on Computing |language=en |volume=10 |issue=3 |pages=456–464 |doi=10.1137/0210033 |issn=0097-5397}}</ref>