Subset-Sum Problem
Exponential-time exact algorithm

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).

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
  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
  do J = 1 to P; L.J = M.J; end
return L.P


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)

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

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 


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


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

cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.