{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T16:49:13Z","timestamp":1664642953816},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1974,4]]},"abstract":"\n Given\n r<\/jats:italic>\n numbers\n s<\/jats:italic>\n 1<\/jats:sub>\n , \u2026,\n \n s\n r<\/jats:sub>\n <\/jats:italic>\n , algorithms are investigated for finding all possible combinations of these numbers which sum to\n M<\/jats:italic>\n . 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\n <\/jats:p>","DOI":"10.1145\/321812.321823","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:10Z","timestamp":1027769170000},"page":"277-292","source":"Crossref","is-referenced-by-count":310,"title":["Computing Partitions with Applications to the Knapsack Problem"],"prefix":"10.1145","volume":"21","author":[{"given":"Ellis","family":"Horowitz","sequence":"first","affiliation":[{"name":"Computer Science Program, University of Southern Califorina, Los Angles, CA and Cornell University, Ithaca, New York"}]},{"given":"Sartaj","family":"Sahni","sequence":"additional","affiliation":[{"name":"Department of CICS, Unversity of Minnesota, Minneapolis MN and Cornell University, Ithaca, New York"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","volume-title":"Applied Combinatorial Mathematics","author":"BECKENBACH E. F.","year":"1964"},{"key":"e_1_2_1_2_2","first-page":"1","article-title":"Transformation of integer programs to knapsack problems","volume":"1","author":"BRAI LI.","year":"1971","journal-title":"Discrete Math"},{"key":"e_1_2_1_3_2","first-page":"151","volume-title":"Conf. Record of Third ACM Symposium on Theory of Computing","author":"STI PHI","year":"1970"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1287\/opre.13.1.94","article-title":"Multistage cutting stock problems of two and more dimensions","volume":"13","author":"GILMOR~","year":"1965","journal-title":"Oper. Res."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1287\/opre.14.6.1045","article-title":"The theory and computation of knapsack functions","volume":"14","author":"GILMORE P. C.","year":"1966","journal-title":"Oper. Re8"},{"key":"e_1_2_1_6_2","first-page":"5","article-title":"NBI,:nO, H., AND HEOEmCH, R.L. A branch search algorithm for the knapsack problem","volume":"16","author":"E~","year":"1970","journal-title":"Manage. Sci."},{"key":"e_1_2_1_7_2","volume-title":"A~ Introduction to the Theory of Numbers","author":"HARDY G. H.","year":"1959","edition":"4"},{"key":"e_1_2_1_8_2","unstructured":"INGAnGIOL~ G. P. Am) KonsH J. F. A reduction algorithm for zero-one single knapsack problems. Manage. Sci. (to appear). INGAnGIOL~ G. P. Am) KonsH J. F. A reduction algorithm for zero-one single knapsack problems. Manage. Sci. (to appear)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","first-page":"85","volume-title":"Complexity of Computer Computa. tious","author":"KARP R.","year":"1972","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_10_2","first-page":"723","article-title":"SAR, P. J. A branch and bound algorithm for the knapsack problem","volume":"13","author":"KOL","year":"1967","journal-title":"Manage. Sci."},{"key":"e_1_2_1_11_2","volume-title":"A method for solving discrete optimisation problems. Oper. Res. 1,~","author":"LAWLI R, E","year":"1966"},{"key":"e_1_2_1_12_2","volume-title":"U. of Wisconsin","author":"ER ID R","year":"1971"},{"key":"e_1_2_1_13_2","first-page":"9","article-title":"R, G. L., ^ND ULLMAN, Z. Discrete dynamic programming a1~d capital allocation","volume":"15","author":"NEMHAUSI.","year":"1969","journal-title":"Manage. Sci."},{"key":"e_1_2_1_14_2","volume-title":"17deger Programming","author":"NEMHAUS R, G","year":"1972"},{"key":"e_1_2_1_15_2","volume-title":"Methods for the solution of the multi-dimensional 0\/1 knapsack problem. Oper. Res. 15, 1 (Jan.-Feb","author":"W~ N{.","year":"1967"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321812.321823","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T21:37:04Z","timestamp":1614721024000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321812.321823"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,4]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1974,4]]}},"alternative-id":["10.1145\/321812.321823"],"URL":"http:\/\/dx.doi.org\/10.1145\/321812.321823","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1974,4]]}}}