A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem

Silvano Martello and Paolo Toth
Additional contact information
Silvano Martello: Istituto di Automatica, University of Bologna, Bologna, Italy
Paolo Toth: Istituto di Informatica e Sistemistica, University of Firenze, Firenze, Italy

Management Science, 1984, vol. 30, issue 6, 765-771

Abstract: 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.

Keywords: programming: integer algorithms; branch and bound/dynamic programming (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.30.6.765 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:30:y:1984:i:6:p:765-771

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().