Subset-Sum Problem
Exact algorithm - Dynamic programming
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).
ALGORITHM
The time complexity of the following exact algorihm is O(MIN(2**(N+1),N*T). The algorithm encodes the result as bit string. For example:
N=10; T = 69
A.1 = 5; A.2 = 9; A.3 = 13; A.4 = 4; A.5 = 1
A.6 = 17; A.7 = 11; A.8 = 2; A.9 = 3; A.10 = 12
|
The result is 743, it is the bit string 1011100111 and it means that elements with indexes (read the bit string from the right to the left) 1, 2, 3, 6, 7, 8, 10 belong to subset. Proof: A.1 (5) + A.2 (9) + A.3 (13) + A.6 (17) + A.7 (11) + A.8 (2) + A.10 (12) = 69
IMPLEMENTATION
Unit: internal subroutine
Global variables: array A.1,...,A.N of positive integers, output array X.
Parameters:
a positive integer N, a positive integer T
Result:
output array X., where X.J=1 if item A.J is selected; or X.J=0 otherwise (for J=1,...,N)
DPS: procedure expose A. X.
parse arg N, T
/* for N <= 10000 */
numeric digits 3011; Nd = 2 ** N - 1
numeric digits LENGTH(Nd)
A1.0 = 0; X.0 = 0; S = 1
B = 2; A1.1 = A.1; X.1 = 1; M = 2
do until M > N | A1.S = T
I = 0; K = 0; H = 1
Y = A.M; Sp1 = S + 1; A1.Sp1 = 1E+100
A2.0 = 0; X2.0 = 0
do while MIN(Y, A1.H) <= T
K = K + 1
if A1.H <= Y
then do
A2.K = A1.H; X2.K = X.H; H = H + 1
end
else do
A2.K = Y; X2.K = X.I + B
end
if A2.K = Y
then do
I = I + 1; Y = A1.I + A.M
end
end
S = K; B = 2 * B
do J = 1 to S
A1.J = A2.J; X.J = X2.J
end
M = M + 1
end
BinXS = X.S
do J = 1 while BinXS > 0
X.J = BinXS // 2
BinXS = BinXS % 2
end
do J = J to N; X.J = 0; end
return
|
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 diofantine equations.
Notes:
| 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 |
CONNECTIONS
Literature
Martello S., Toth P. Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990
