  We formulate the knapsack problem (KP) as a statistical physics system and
compute the corresponding partition function as an integral in the complex
plane. The introduced formalism allows us to derive three
statistical-physics-based algorithms for the KP: one based on the recursive
definition of the exact partition function; another based on the large weight
limit of that partition function; and a final one based on the zero-temperature
limit of the second. Comparing the performances of the algorithms, we find that
they do not consistently outperform (in terms of runtime and accuracy) dynamic
programming, annealing, or standard greedy algorithms. However, the exact
partition function is shown to reproduce the dynamic programming solution to
the KP, and the zero-temperature algorithm is shown to produce a greedy
solution. Therefore, although dynamic programming and greedy solutions to the
KP are conceptually distinct, the statistical physics formalism introduced in
this work reveals that the large weight-constraint limit of the former leads to
the latter. We conclude by discussing how to extend this formalism in order to
obtain more accurate versions of the introduced algorithms and to other similar
combinatorial optimization problems.
