A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
Management Science · 1984 · Volume 30 · Issue 6
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
Enable JavaScript for citation tools and additional paper interactions.