The Knapsack Problem: Some Relations for an Improved Algorithm

摘要

The knapsack problem has traditionally been solved by dynamic programming, though a more recent enumerative algorithm by P. C. Gilmore and R. E. Gomory has proved somewhat more efficient. In this paper relations are developed which substantially reduce the number of solutions which must be examined by the Gilmore-Gomory method, or by any algorithm for the knapsack problem which uses an enumerative base. Our results enable certain problems for which the Gilmore-Gomory method reduces almost to complete enumeration to be solved after examining only a handful of alternatives. Computer studies to provide detailed comparisons of methods which do and do not employ these results have not yet been undertaken. (Author)