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.

• 저널Management Science · 30(6) · 765–771
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.30.6.765
• 저자Silvano Martello, Paolo Toth