DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
THE KNAPSACK PROBLEM: SOME RELATIONS FOR AN IMPROVED ALGORITHM
CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION
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.
Management sciences research rept.
Approved for public release; distribution is unlimited. Document partially illegible.