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

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

mail