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