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.
Accession Number:
AD0610380
Title:
THE KNAPSACK PROBLEM: SOME RELATIONS FOR AN IMPROVED ALGORITHM
Corporate Author:
CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION
Report Date:
1965-01-01
Abstract:
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.
Descriptive Note:
Management sciences research rept.
Supplementary Note:
DOI: 10.21236/AD0610380
Pages:
0027
Distribution Statement:
Approved for public release; distribution is unlimited. Document partially illegible.
Contract Number:
NONR-760(24)
File Size:
2.49MB
