### Computing Partitions with Applications to the Knapsack ProblemComputing Partitions with Applications to the Knapsack Problem

Access Restriction
Subscribed

 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

Source: ACM Digital Library