Access Restriction

Author Horowitz, Ellis ♦ Sahni, Sartaj
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1974
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Given $\textit{r}$ numbers $\textit{s}1,$ ···, $\textit{sr},$ algorithms are investigated for finding all possible combinations of these numbers which sum to $\textit{M}.$ This problem is a particular instance of the 0-1 unidimensional knapsack problem. All of the usual algorithms for this problem are investigated in terms of both asymptotic computing times and storage requirements, as well as average computing times. We develop a technique which improves all of the dynamic programming methods by a square root factor. Empirical studies indicate this new algorithm to be generally superior to all previously known algorithms. We then show how this improvement can be incorporated into the more general 0-1 knapsack problem obtaining a square root improvement in the asymptotic behavior. A new branch and search algorithm that is significantly faster than the Greenberg and Hegerich algorithm is also presented. The results of extensive empirical studies comparing these knapsack algorithms are given
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1974-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 21
Issue Number 2
Page Count 16
Starting Page 277
Ending Page 292

Open content in new tab

   Open content in new tab
Source: ACM Digital Library