A New Algorithm for the 0-1 Knapsack Problem
提出一种针对0-1背包问题的新算法，通过确定核心子集并求解，得到高概率最优的启发式解，适用于大规模问题，并提供了Fortran代码。
We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding “core problem”: from this we derive a heuristic solution for the original problem which, with high probability, can be proved to be optimal. The algorithm incorporates a new method of computation of upper bounds and efficient implementations of reduction procedures. The corresponding Fortran code is available. We report computational experiments on small-size and large-size random problems, comparing the proposed code with all those available in the literature.