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

Publisher Website
Google Scholar
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.programming: integer algorithms, branch and bound/dynamic programming

This publication has 0 references indexed in Scilit: