Subset-Sum Problem
Exponential-time exact algorithm

PROBLEM
In the subset-sum problem we wish to find a subset of A.1,...,A.N whose sum is as large as possible but not larger than T (capacity of the knapsack).

IMPLEMENTATION
Unit: internal function

Global variables: array A.1,...,A.N of positive integers, array A. is not changed

Parameters: a positive integer N, a positive integer T

Returns: largest sum of subset <=T

 EXACT_SUBSET_SUM: procedure expose A. parse arg N, T L.1 = 0; P = 1; Sentinel = 1E+100 do I = 1 to N while A.I <= T   do J = 1 to P     LP.J = L.J + A.I     if LP.J > T then leave J   end   R = J - 1; K = 1; L = 1   P = P + R; Pp1 = P + 1   L.Pp1 = Sentinel; LP.J = Sentinel   do M = 1 to P     if L.K < LP.L       then do; M.M = L.K; K = K + 1; end       else do; M.M = LP.L; L = L + 1; end   end   do J = 1 to P; L.J = M.J; end end return L.P

COMPARISON
For N=100;T=25557 and the array A. created by statements:

 Seed = RANDOM(1, 1, 481989) do J = 1 to N  A.J = RANDOM(1, 1000)end

I compared the algorithms for solution of the Subset-sum problem and my algorithm DIOPHANT for solution of the diophantine equations.

Notes:
I halted the EXACT_SUBSET_SUM after 30 minutes of computations. For APPROX_SUBSET_SUM I used the value Epsilon=0.5

Subset-sum problem - Comparison of Algorithms
Algorithm Subset sum Seconds
GS 25554      0.05
DPS 25557   240.24
APPROX_SUBSET_SUM 25436    12.31
DIOPHANT 25557      0.82

CAUTION
EXACT_SUBSET_SUM is suitable only for N<20. For N=15,16,17 function required 4,30,144 seconds.

SOUVISLOSTI

Literature
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990

 cover contents index main page