1974/04/01 by Ellis Horowitz, Sartaj Sahni · 2 citations
Engineering · Computer Science · #Optimization and Packing Problems #Optimization and Search Problems #Computational Geometry and Mesh Generation
paper · pdf · doi:10.1145/321812.321823
openalex publication_date 1974/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Given r numbers s 1 , …, s r , algorithms are investigated for finding all possible combinations of these numbers which sum to 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