An exact algorithm for the subset sum problem

doi:10.1016/S0377-2217(00)00329-5

An exact algorithm for the subset sum problem

2002-01-01

15

PRE

AI

DOI：10.1016/S0377-2217(00)00329-5

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

combinatorial optimization

subset sum problem

dynamic programming

core problem

binary tree

An exact algorithm for the subset sum problem

Abstract

AI Summary

Journal

Organization