PROBLÉM SOUČTU PODMNOŽIN
PŘESNÉ ŘEŠENÍ - DYNAMICKÉ PROGRAMOVÁNÍ
PROBLÉM
Chceme najít podmnožinu množiny A.1,...,A.N, jejíž součet je největší možný, ale ne větší než T (T je tzv. velikost batohu).
ALGORITMUS
Časová složitost následujícího algoritmu je O(MIN(2**(N+1),N*T). Algoritmus kóduje výsledek jako bitový řetězec. Například:
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
|
Výsledek je 743; vyjádřeno jako bitový řetězec 1011100111. To znamená, že do hledané podmnožiny patří prvky s indexy (bitový řetězec je třeba číst zprava doleva) 1, 2, 3, 6, 7, 8, 10. Důkaz: A.1 (5) + A.2 (9) + A.3 (13) + A.6 (17) + A.7 (11) + A.8 (2) + A.10 (12) = 69
IMPLEMENTACE
Jednotka: vnitřní podprogram
Globální proměnné: pole A.1,...,A.N přirozených čísel, výstupní pole X.
Parametry: přirozená čísla N a T
Výsledek:
výstupní pole X., pro ksždé J=1,...,N platí: X.J=1, jestliže prvek A.J patří do hledané podmnožiny, X.J=0 jinak
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
|
POROVNÁNÍ
Pro N=100;T=25557 a pole A. vytvořené příkazy:
Seed = RANDOM(1, 1, 481989)
do J = 1 to N
A.J = RANDOM(1, 1000)
end
|
jsem porovnal algoritmy pro řešení problému součtu podmnožin a můj algoritmus
DIOPHANT pro řešení Diofantovy rovnice.
Poznámky:
| Součet podmnožin - porovnání algoritmů |
| Algoritmus |
Suma prvků |
Sekund |
| GS |
25554 |
0.05 |
| DPS |
25557 |
240.24 |
| APPROX_SUBSET_SUM |
25436 |
12.31 |
| DIOPHANT |
25557 |
0.82 |
SOUVISLOSTI
Literatura
Martello S., Toth P. Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990
