Algorytmy wyklady, Algorytmy zachłanne (greedy algorithms), ALGORYTMY ZACHŁANNE (GREEDY ALGORITHMS)


ALGORYTMY ZACHŁANNE (GREEDY ALGORITHMS)

GREEDY-ACTIVITY-SELECTOR ( s, f );

{ s, f są tablicami jednowymiarowymi; zakładamy, ze f [1] ≤ f [2] ≤ ...≤ f [n] }

begin

n := length [s];

A := {1};

j := 1;

for i := 2 to n do

if s [i] ≥ f [j] then

begin

A := A ∪ {i};

j := i

end;

return A;

end;



Wyszukiwarka