Editing Knapsack problem (section)

=== Approximation Algorithms ===
As for most NP-complete problems, it may be enough to find workable solutions even if they are not optimal. Preferably, however, the approximation comes with a guarantee of the difference between the value of the solution found and the value of the optimal solution.

As with many useful but computationally complex algorithms, there has been substantial research on creating and analyzing algorithms that approximate a solution. The knapsack problem, though NP-Hard, is one of a collection of algorithms that can still be approximated to any specified degree. This means that the problem has a polynomial time approximation scheme. To be exact, the knapsack problem has a [[fully polynomial time approximation scheme]] (FPTAS).<ref name="Vazirani, Vijay 2003">Vazirani, Vijay. Approximation Algorithms. Springer-Verlag Berlin Heidelberg, 2003.</ref>

==== Greedy approximation algorithm ====
[[George Dantzig]] proposed a [[greedy algorithm|greedy]] [[approximation algorithm]] to solve the unbounded knapsack problem.<ref name="dantzig1957">{{cite journal | last1 = Dantzig | first1 = George B. | author-link = George Dantzig | year = 1957 | title = Discrete-Variable Extremum Problems | journal = Operations Research | volume = 5 | issue = 2| pages = 266–288 | doi = 10.1287/opre.5.2.266 }}</ref> His version sorts the items in decreasing order of value per unit of weight, <math>v_1/w_1\ge\cdots\ge v_n/w_n</math>. It then proceeds to insert them into the sack, starting with as many copies as possible of the first kind of item until there is no longer space in the sack for more. Provided that there is an unlimited supply of each kind of item, if <math>m</math> is the maximum value of items that fit into the sack, then the greedy algorithm is guaranteed to achieve at least a value of <math>m/2</math>.

For the bounded problem, where the supply of each kind of item is limited, the above algorithm may be far from optimal. Nevertheless, a simple modification allows us to solve this case: Assume for simplicity that all items individually fit in the sack (<math>w_i \le W</math> for all <math>i</math>). Construct a solution <math>S_1</math> by packing items greedily as long as possible, i.e. <math>S_1=\left\{1,\ldots,k\right\}</math> where <math>k=\textstyle\max_{1\le k'\le n}\textstyle\sum_{i=1}^{k'} w_i\le W</math>. Furthermore, construct a second solution <math>S_2=\left\{k+1\right\}</math> containing the first item that did not fit. Since <math>S_1\cup S_2</math> provides an upper bound for the [[Linear programming relaxation|LP relaxation]] of the problem, one of the sets must have value at least <math>m/2</math>; we thus return whichever of <math>S_1</math> and <math>S_2</math> has better value to obtain a <math>1/2</math>-approximation.

It can be shown that the average performance converges to the optimal solution in distribution at the error rate <math> n^{-1/2}</math> <ref>{{cite journal |last1=Calvin |first1=James M. |last2=Leung |first2=Joseph Y. -T. |title=Average-case analysis of a greedy algorithm for the 0/1 knapsack problem |journal=Operations Research Letters |date=1 May 2003 |volume=31 |issue=3 |pages=202–210 |doi=10.1016/S0167-6377(02)00222-5 }}</ref>

==== Fully polynomial time approximation scheme ====
The [[fully polynomial time approximation scheme]] (FPTAS) for the knapsack problem takes advantage of the fact that the reason the problem has no known polynomial time solutions is because the profits associated with the items are not restricted. If one rounds off some of the least significant digits of the profit values then they will be bounded by a polynomial and 1/ε where ε is a bound on the correctness of the solution. This restriction then means that an algorithm can find a solution in polynomial time that is correct within a factor of (1-ε) of the optimal solution.<ref name="Vazirani, Vijay 2003"/>

 '''algorithm''' FPTAS '''is''' 
     '''input:''' ε ∈ (0,1]
            a list A of n items, specified by their values, <math>v_i</math>, and weights
     '''output:''' S' the FPTAS solution
 
     P := max <math>\{v_i\mid 1 \leq i \leq n\} </math>  // the highest item value
     K := ε <math>\frac{P}{n}</math>
 
     '''for''' i '''from''' 1 '''to''' n '''do'''
         <math>v'_i</math> := <math>\left\lfloor \frac{v_i}{K} \right\rfloor</math>
     '''end for'''
 
     '''return''' the solution, S', using the <math>v'_i</math> values in the dynamic program outlined above

'''Theorem:''' The set <math>S'</math> computed by the algorithm above satisfies <math>\mathrm{profit}(S') \geq (1-\varepsilon) \cdot \mathrm{profit}(S^*)</math>, where <math>S^*</math> is an optimal solution.

====Quantum approximate optimization====
[[Quantum approximate optimization algorithm]] (QAOA) can be employed to solve Knapsack problem using [[quantum computation]] by minimizing the [[Hamiltonian (quantum mechanics)|Hamiltonian]] of the problem. The Knapsack Hamiltonian is constructed via embedding the constraint condition to the cost function of the problem with a penalty term.<ref>{{Cite journal |last=Lucas |first=Andrew |date=2014 |title=Ising formulations of many NP problems |journal=Frontiers in Physics |volume=2 |page=5 |doi=10.3389/fphy.2014.00005 |doi-access=free |arxiv=1302.5843 |bibcode=2014FrP.....2....5L |issn=2296-424X}}</ref><math display="block">
{H} = -\sum_{i=1}^n v_i x_i + P \left(\sum_{i=1}^n w_i x_i - W\right)^2, 
</math>where <math>
P 
</math> is the penalty constant which is determined by case-specific fine-tuning.