A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
Given n items, each having a weight w i, and a container of capacity W, the Subset-Sum Problem (SSP) is to select a subset of the items whose total weight is closest to, without exceeding, W. The paper presents a mixed approach (depth first search-dynamic programming) to the exact solution of the problem. An extensive computational experience is presented, comparing the proposed algorithm with that of Ahrens-Finke, as well as with the Balas-Zemel algorithm for large problems. Both "easy" and "hard" problems with values of n up to 10,000 are considered.
Volume (Year): 30 (1984)
Issue (Month): 6 (June)
|Contact details of provider:|| Postal: |
Web page: http://www.informs.org/Email:
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:30:y:1984:i:6:p:765-771. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc)
If references are entirely missing, you can add them using this form.