A STATISTICAL-ANALYSIS OF THE KNAPSACK-PROBLEM

We investigate the dependence of the multi-knapsack objective function on the knapsack capacities and on the number of capacity constraints P, in the case when all N objects are assigned the same profit value a nd the weights are uniformly distributed over the unit interval. A rig orous upper bound to the optimal profit is obtained employing the anne aled approximation and then compared with the exact value obtained thr ough the Lagrangian relaxation method. The analysis is restricted to t he regime where N goes to infinity and P remains finite.