haku: @author Toth, P. / yhteensä: 13
viite: 6 / 13
Tekijä: | Martello, S. Toth, P. |
Otsikko: | A new algorithm for the 0-1 knapsack problem. |
Lehti: | Management Science
1988 : MAY, VOL. 34:5, p. 633-644 |
Asiasana: | KNAPSACK PROBLEM ALGORITHMS |
Kieli: | eng |
Tiivistelmä: | There is 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 one derives 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. |
SCIMA