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:
Provádění EXACT_SUBSET_SUM jsem násilně ukončil po půl hodině. Pro běh APPROX_SUBSET_SUM jsem zvolil hodnotu Epsilon=0.5

 

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


Obálka Obsah Index Hlavní stránka

změněno 8. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.