Editing Knapsack problem (section)

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