An exact algorithm for the subset sum problem

The subset sum problem (SSP) is defined as: "Given n positive integers w(1),..., w(n), find a combination amongst them such that their sum is the closest to, but not exceeding, a positive integer c". We suggest an exact algorithm by introducing a new type of Core Problem and also, by using an improved version of Bellman's recursion. We show that the resulting algorithm is bounded in time and space resource utilizations, respectively, by O(Max{(n - log(2)c(2))c, clog(2)c}) and O(n + c). In addition to the sharp memory requirement decrease in comparison with any dynamic programming-based algorithm, the search space, for a vast range of instances, is restricted only to feasible states. (C) 2002 Elsevier Science B.V. All rights reserved.