Editing Knapsack problem (section)

== Solving ==
Several algorithms are available to solve knapsack problems, based on the dynamic programming approach,<ref name="eduk2000">{{cite journal | last1 = Andonov | first1 = Rumen | last2 = Poirriez | first2 = Vincent | last3 = Rajopadhye | first3 = Sanjay | year = 2000 | title = Unbounded Knapsack Problem : dynamic programming revisited | journal = European Journal of Operational Research | volume = 123 | issue = 2 | pages = 168–181 | doi = 10.1016/S0377-2217(99)00265-9 | citeseerx = 10.1.1.41.2135 }}</ref> the [[branch and bound]] approach<ref name="martellototh90">S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations,
John Wiley and Sons, 1990</ref> or [[hybrid algorithm|hybridizations]] of both approaches.<ref name="poirriez_et_all_2009"/><ref name="martellopisingertoth99a">S. Martello, D. Pisinger, P. Toth, [https://www.jstor.org/stable/pdf/2634886.pdf Dynamic programming and strong bounds for the 0-1 knapsack problem], ''Manag. Sci.'', 45:414–424, 1999.</ref><ref name="plateau85">{{cite journal | last1 = Plateau | first1 = G. | last2 = Elkihel | first2 = M. | year = 1985 | title = A hybrid algorithm for the 0-1 knapsack problem | journal = Methods of Oper. Res. | volume = 49 | pages = 277–293 }}</ref><ref name="martellotothe99">{{cite journal | last1 = Martello | first1 = S. | last2 = Toth | first2 = P. | year = 1984| title = A mixture of dynamic programming and branch-and-bound for the subset-sum problem | journal = Manag. Sci. | volume = 30 | issue = 6| pages = 765–771 | doi=10.1287/mnsc.30.6.765}}</ref>

=== Dynamic programming in-advance algorithm ===
The '''unbounded knapsack problem''' ('''UKP''') places no restriction on the number of copies of each kind of item. Besides, here we assume that <math>x_i > 0</math>
: <math>m[w']= \max \left( \sum_{i=1}^n v_i x_i \right)</math>
: subject to <math>\sum_{i=1}^n w_i x_i \leq w'</math> and <math>x_i > 0</math>

Observe that <math>m[w]</math> has the following properties:

1. <math>m[0]=0\,\!</math> (the sum of zero items, i.e., the summation of the empty set).

2. <math>m[w]=\max (v_1+m[w-w_1],v_2+m[w-w_2],...,v_n+m[w-w_n])</math>
, <math>w_i \leq w</math>, where <math>v_i</math> is the value of the <math>i</math>-th kind of item.

The second property needs to be explained in detail. During the process of the running of this method, how do we get the weight <math>w</math>? There are only <math>i</math> ways and the previous weights are <math>w-w_1, w-w_2,..., w-w_i</math> where there are total <math>i</math> kinds of different item (by saying different, we mean that the weight and the value are not completely the same). If we know each value of these <math>i</math> items and the related maximum value previously, we just compare them to each other and get the maximum value ultimately and we are done.

Here the maximum of the empty set is taken to be zero. Tabulating the results from <math>m[0]</math> up through <math>m[W]</math> gives the solution. Since the calculation of each <math>m[w]</math> involves examining at most <math>n</math> items, and there are at most <math>W</math> values of <math>m[w]</math> to calculate, the running time of the dynamic programming solution is [[Big O notation|<math>O(nW)</math>]]. Dividing <math>w_1,\,w_2,\,\ldots,\,w_n,\,W</math> by their [[greatest common divisor]] is a way to improve the running time.

Even if [[P versus NP problem|P≠NP]], the <math>O(nW)</math> complexity does not contradict the fact that the knapsack problem is [[NP-complete]], since <math>W</math>, unlike <math>n</math>, is not polynomial in the length of the input to the problem. The length of the <math>W</math> input to the problem is proportional to the number of bits in <math>W</math>, <math>\log W</math>, not to <math>W</math> itself. However, since this runtime is [[pseudopolynomial]], this makes the (decision version of the) knapsack problem a [[weak NP-completeness|weakly NP-complete problem]].

==== 0-1 knapsack problem ====
[[File:Knapsack problem dynamic programming.gif|alt=A demonstration of the dynamic programming approach.|thumb|A demonstration of the dynamic programming approach.]]
A similar dynamic programming solution for the 0-1 knapsack problem also runs in pseudo-polynomial time. Assume <math>w_1,\,w_2,\,\ldots,\,w_n,\, W</math> are strictly positive integers. Define <math>m[i,w]</math> to be the maximum value that can be attained with weight less than or equal to <math>w</math> using items up to <math>i</math> (first <math>i</math> items).

We can define <math>m[i,w]</math> recursively as follows: '''(Definition A)'''
* <math>m[0,\,w]=0</math>
* <math>m[i,\,w]=m[i-1,\,w]</math> if <math>w_i > w\,\!</math> (the new item is more than the current weight limit)
*<math>m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)</math> if <math>w_i \leqslant w</math>.

The solution can then be found by calculating <math>m[n,W]</math>. To do this efficiently, we can use a table to store previous computations.

The following is pseudocode for the dynamic program:

<syntaxhighlight lang="c" line>
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W];
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 1 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

</syntaxhighlight>

This solution will therefore run in <math>O(nW)</math> time and <math>O(nW)</math> space. 
(If we only need the value m[n,W], we can modify the code so that the amount of memory required is O(W) which stores the recent two lines of the array "m".)

However, if we take it a step or two further, we should know that the method will run in the time between <math>O(nW)</math> and <math>O(2^n)</math>. From '''Definition A''', we know that there is no need to compute all the weights when the number of items and the items themselves that we chose are fixed. That is to say, the program above computes more than necessary because the weight changes from 0 to W often. From this perspective, we can program this method so that it runs recursively.

<syntaxhighlight lang="c" line="1">
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

Define value[n, W]

Initialize all value[i, j] = -1

Define m:=(i,j)         // Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
{
    if i == 0 or j <= 0 then:
        value[i, j] = 0
        return

    if (value[i-1, j] == -1) then:     // m[i-1, j] has not been calculated, we have to call function m
        m(i-1, j)

    if w[i] > j then:                      // item cannot fit in the bag
        value[i, j] = value[i-1, j]
    else: 
        if (value[i-1, j-w[i]] == -1) then:     // m[i-1,j-w[i]] has not been calculated, we have to call function m
            m(i-1, j-w[i])
        value[i, j] = max(value[i-1,j], value[i-1, j-w[i]] + v[i])
}

Run m(n, W)
</syntaxhighlight>

For example, there are 10 different items and the weight limit is 67. So,
<math display=block>\begin{align}
&w[  1]= 23 ,w[  2]= 26,w[  3]= 20,w[  4]= 18,w[  5]= 32,w[  6]= 27,w[  7]= 29,w[  8]= 26,w[  9]= 30,w[ 10]= 27 \\
&v[  1]=505 ,v[  2]=352,v[  3]=458,v[  4]=220,v[  5]=354,v[  6]=414,v[  7]=498,v[  8]=545,v[  9]=473,v[ 10]=543 \\
\end{align}</math>
If you use above method to compute for <math>m(10,67)</math>, you will get this, excluding calls that produce <math>m(i,j) = 0</math>:
<math display=block>\begin{align}
&m(10, 67) = 1270\\
&m(9, 67) = 1270, m(9, 40) = 678\\
&m(8, 67) = 1270, m(8, 40) = 678, m(8, 37) = 545\\
&m(7, 67) = 1183, m(7, 41) = 725, m(7, 40) = 678, m(7, 37) = 505\\
&m(6, 67) = 1183, m(6, 41) = 725, m(6, 40) = 678, m(6, 38) = 678, m(6, 37) = 505\\
&m(5, 67) = 1183, m(5, 41) = 725, m(5, 40) = 678, m(5, 38) = 678, m(5, 37) = 505\\
&m(4, 67) = 1183, m(4, 41) = 725, m(4, 40) = 678, m(4, 38) = 678, m(4, 37) = 505, m(4, 35) = 505\\
&m(3, 67) = 963, m(3, 49) = 963, m(3, 41) = 505, m(3, 40) = 505, m(3, 38) = 505, m(3, 37) = 505, m(3, 35) = 505, m(3, 23) = 505, m(3, 22) = 458, m(3, 20) = 458\\
&m(2, 67) = 857, m(2, 49) = 857, m(2, 47) = 505, m(2, 41) = 505, m(2, 40) = 505, m(2, 38) = 505, m(2, 37) = 505, m(2, 35) = 505, m(2, 29) = 505, m(2, 23) = 505\\
&m(1, 67) = 505, m(1, 49) = 505, m(1, 47) = 505, m(1, 41) = 505, m(1, 40) = 505, m(1, 38) = 505, m(1, 37) = 505, m(1, 35) = 505, m(1, 29) = 505, m(1, 23) = 505\\
\end{align}</math>

Besides, we can break the recursion and convert it into a tree. Then we can cut some leaves and use [[parallel computing]] to expedite the running of this method.

To find the actual subset of items, rather than just their total value, we can run this after running the function above:<syntaxhighlight lang="c" line="1">
/**
 * Returns the indices of the items of the optimal knapsack.
 * i: We can include items 1 through i in the knapsack
 * j: maximum weight of the knapsack
 */
function knapsack(i: int, j: int): Set<int> {
    if i == 0 then:
        return {}
    if m[i, j] > m[i-1, j] then:
        return {i} ∪ knapsack(i-1, j-w[i])
    else:
        return knapsack(i-1, j)
}

knapsack(n, W)
</syntaxhighlight>

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

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

===Dominance relations===
Solving the unbounded knapsack problem can be made easier by throwing away items which will never be needed.  For a given item <math>i</math>, suppose we could find a set of items <math>J</math> such that their total weight is less than the weight of <math>i</math>, and their total value is greater than the value of <math>i</math>.  Then <math>i</math> cannot appear in the optimal solution, because we could always improve any potential solution containing <math>i</math> by replacing <math>i</math> with the set <math>J</math>.  Therefore, we can disregard the <math>i</math>-th item altogether.  In such cases, <math>J</math> is said to '''dominate''' <math>i</math>.  (Note that this does not apply to bounded knapsack problems, since we may have already used up the items in <math>J</math>.)

Finding dominance relations allows us to significantly reduce the size of the search space.  There are several different types of [[dominance relations]],<ref name="poirriez_et_all_2009" /> which all satisfy an inequality of the form:

<math>\qquad \sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i</math>, and <math>\sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\,</math> for some <math>x \in Z _+^n </math>

where
<math>\alpha\in Z_+ \,,J\subsetneq N</math> and <math>i\not\in J</math>.  The vector <math>x</math> denotes the number of copies of each member of <math>J</math>.

;Collective dominance:  The <math>i</math>-th item is  '''collectively dominated''' by <math>J</math>, written as <math>i\ll J</math>, if the total weight of some combination of items in <math>J</math> is less than ''w<sub>i</sub>'' and their total value is greater than ''v<sub>i</sub>''.  Formally, <math>\sum_{j \in J} w_j\,x_j \ \le  w_i</math> and <math>\sum_{j \in J} v_j\,x_j \ \ge v_i</math> for some <math>x \in Z _+^n </math>, i.e. <math>\alpha=1</math>.  Verifying this dominance is computationally hard, so it can only be used with a dynamic programming approach.  In fact, this is equivalent to solving a smaller knapsack decision problem where <math>V = v_i</math>, <math>W = w_i</math>, and the items are restricted to <math>J</math>.
;Threshold dominance: The <math>i</math>-th item is '''threshold dominated'''  by <math>J</math>, written as <math>i\prec\prec J</math>, if some number of copies of <math>i</math> are dominated by <math>J</math>.  Formally, <math>\sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i</math>, and <math>\sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\,</math> for some <math>x \in Z _+^n </math> and <math>\alpha\geq 1</math>.  This is a generalization of collective dominance, first introduced in<ref name="eduk2000"/> and used in the EDUK algorithm.  The smallest such <math>\alpha</math> defines the '''threshold''' of the item <math>i</math>, written  <math>t_i =(\alpha-1)w_i</math>.  In this case, the optimal solution could contain at most <math>\alpha-1</math> copies of <math>i</math>.
;Multiple dominance: The <math>i</math>-th item is  '''multiply dominated''' by a single item <math>j</math>, written as <math>i\ll_{m} j</math>, if <math>i</math> is dominated by some number of copies of <math>j</math>.  Formally, <math>w_j\,x_j \ \le  w_i</math>, and <math>v_j\,x_j \ \ge v_i</math> for some <math>x_j \in Z _+ </math> i.e. <math> J=\{j\}, \alpha=1,  x_j=\lfloor \frac{w_i}{w_j}\rfloor</math>. This dominance could be efficiently used during preprocessing because it can be detected relatively easily.
;Modular dominance: Let <math>b</math> be the ''best item'', i.e. <math>\frac{v_b}{w_b}\ge\frac{v_i}{w_i}\, </math> for all <math>i</math>.  This is the item with the greatest density of value. The <math>i</math>-th item is '''modularly dominated''' by a single item <math>j</math>, written as <math>i\ll_\equiv j</math>, if <math>i</math> is dominated by <math>j</math> plus several copies of <math>b</math>.  Formally, <math> w_j+tw_b \le w_i</math>, and  <math>v_j +tv_b \ge v_i </math> i.e. <math>J=\{b,j\}, \alpha=1,  x_b=t, x_j=1</math>.