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
|
