Editing Knapsack problem (section)

===Unit-cost models===
The NP-hardness of the Knapsack problem relates to computational models in which the size of integers matters (such as the [[Turing machine]]). In contrast, [[decision tree model|decision trees]] count each decision as a single step. Dobkin and Lipton<ref>{{Cite journal|last1=Dobkin|first1=David|last2=Lipton|first2=Richard J.|year=1978|title=A lower bound of ½''n''<sup>2</sup> on linear search programs for the Knapsack problem|url=https://dx.doi.org/10.1016/0022-0000%2878%2990026-0|journal=Journal of Computer and System Sciences|volume=16|issue=3|pages=413–417|doi=10.1016/0022-0000(78)90026-0}}</ref> show an <math>{1\over 2}n^2</math> lower bound on linear decision trees for the knapsack problem, that is, trees where decision nodes test the sign of [[affine function]]s.<ref>In fact, the lower bound applies to the subset sum problem, which is a special case of Knapsack.</ref> This was generalized to algebraic decision trees by Steele and Yao.<ref>{{Cite journal|last1=Michael Steele|first1=J|last2=Yao|first2=Andrew C|date=1982-03-01|title=Lower bounds for algebraic decision trees|url=https://dx.doi.org/10.1016%2F0196-6774%2882%2990002-5|journal=Journal of Algorithms|language=en|volume=3|issue=1|pages=1–8|doi=10.1016/0196-6774(82)90002-5|issn=0196-6774}}</ref>
If the elements in the problem are [[real number]]s or [[rationals]], the decision-tree lower bound extends to the [[real RAM|real random-access machine]] model with an instruction set that includes addition, subtraction and multiplication of real numbers, as well as comparison and either division or remaindering ("floor").<ref>{{citation|doi=10.1137/S0097539797329397|title=Topological Lower Bounds on Algebraic Random Access Machines|year=2001|last1=Ben-Amram|first1=Amir M.|journal=SIAM Journal on Computing|volume=31|issue=3|pages=722–761|last2=Galil|first2=Zvi|author2-link=Zvi Galil}}.</ref> This model covers more algorithms than the algebraic decision-tree model, as it encompasses algorithms that use indexing into tables. However, in this model all program steps are counted, not just decisions.
An ''upper bound'' for a decision-tree model was given by Meyer auf der Heide<ref>{{citation|doi=10.1145/828.322450|title=A Polynomial Linear Search Algorithm for the ''n''-Dimensional Knapsack Problem|year=1984|last1=auf der Heide|first1=Meyer|journal=Journal of the ACM|volume=31|issue=3|pages=668–676}}</ref> who showed that for every ''n'' there exists an {{math|''O''(''n''<sup>4</sup>)}}-deep linear decision tree that solves the [[#Subset-sum_problem|subset-sum problem]] with ''n'' items. Note that this does not imply any upper bound for an algorithm that should solve the problem for ''any given n''.