Metoda " greedy " in limbajul de programare Pascal

Metoda "greedy" este urmatoarea:

-se initializeaza multimea B lamultimea vida;

-se alege un anumit elemant din A;

-se verifica daca elementul ales poate fi adaugat multimii B;

-procedeul contimua asa, respectiv, pana ce au fost determinate toate elementele din B.

Exista o serie de probleme celebre, in a caror rezolvare se poate folosi aceasta strategie:

-problema continua a rucsacului;

-algoritmul lui Dijkstra pentru drumuri minime.

PROBLEMA CONTUNUA A RUCSACULUI

program Rucsac;

const max=5;

var C,G,X: array [1..max] of Real;

n,i,j:Integer; GG,GGr,aux:Real;

begin

Write(Nr. obiecte = ');

ReadLn (n);

For i:=1 to n do

begin

Write ('C[',i,']=');

ReadLN (c[i]);

Write ('G[',i,']=');

ReadLn (G[i]);

end;

Write('Greut. max. = ');

ReadLn (GG);

for i:=1 to n-1 do

for j:=i+1 to n do

if C[j]/G[j]>C[i]/G[i] then

begin

aux:=C[j]; C[j]:=C[i];

C[i]:=aux; aux:=G[j];

G[j]:=G[i]; G[i]:=aux;

end;

WriteLN('Am ordonat . . .');

for i:=1 to n do

WriteLN('C[',i,']=',C[i] :5:2,

'G[',i,]=' G[i] :5:2,

' ‘,C[i]/G[i] :5:2);

GGr:=GG; i:=1;

While (i<=n) do

if GGr > G[i] then

begin

X[i]:=1;

GGr:=GGr-G[i]; i:=i+1

end

else

begin

X[i]:=GGr/G[i];

For j:=i+1 to n do X[j]:=0

I:=n+1

end;

for i:=1 to n do

WriteLn (‘X[‘,I,’]=’X[i] :5:2);

ReadLn

end.