Statistical mechanics of the knapsack problem
Elka Korutcheva, Manfred Opper, B Lopez · Journal of Physics A Mathematical and General · 1994
The knapsack problem is an NP-complete combinatorial optimization problem with inequality constraints. Using the replica method of statistical physics, we study the space of its solutions for a large problem size. It turns out that this problem is closely related to the theory of the binary perceptron.