PROBLÉM SOUČTU PODMNOŽIN
PŘESNÉ ŘEŠENÍ S EXPONENCIÁLNÍ ČASOVOU SLOŽITOSTÍ

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).

IMPLEMENTACE
Jednotka: vnitřní funkce
 
Globální proměnné: pole A.1,...,A.N přirozených čísel, pole A. se nemění
 
Parametry: přirozená čísla N a T
 
Vrací: největší součet podmnožin <= 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

 

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ě běhu. 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 

 

UPOZORNĚNÍ
EXACT_SUBSET_SUM je vhodný jen pro nevelká pole N<20. Pro N=15,16,17 trvá výpočet po řadě 4,30,144 sekund.

SOUVISLOSTI

Literatura
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990


Obálka Obsah Index Hlavní stránka

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