Editing Knapsack problem (section)

==== 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.