Tehnici de programare

Metoda Greedy

Esenţa metodei:

Fie dată problema P cu spaţiul de soluţii: S = {s1, s2, …, sN}

şi restricţiile R

P cere să se determine în S o submulţime Q* = {q1, q2, …, qK}, astfel încât:

Q* = max {Q1, Q2, …, QR}, R=2N

C

C – criteriul de selecţie soluţiei.

Esenţa metodei (2)

Pentru obţinerea soluţiei Greedy

1. Se sortează elementele din S în măsura descreşterii corespunderii criteriului C. Se obţine şirul sortat: s*1, s*2, …, s*N.

2. Se consideră soluţia iniţial vidă B

3. Se adaugă consecutiv în B elementele s*1, s*2, …, s*i , … atât timp cât nu se încalcă restricţiile R ale problemei P.

Mai puţin formalizat, metoda poate fi descrisă astfel:

Din mulţimea de elemente S se alege acel element s* care satisface cel mai bine criteriul C de includere în soluţie. Dacă adăugarea s* la soluţia curentă nu contravine restricţiilor R ale problemei, acesta se include în soluţie. În caz contrar el se exclude din mulţimea elementelor disponibile pentru adăugare.

Esenţa metodei (3)

Problemă tip

Fie un set S de N (N<100) segmente pe axa 0X.

Pentru fiecare segment si este cunoscută abscisa extremităţii stângi xi şi lungimea sa li.

Să se scrie un program, care va determina un subset cu un număr maxim de segmente, S* S, astfel încât segmentele din S* nu se vor intersecta între ele.

Analiză

Criteriul C: cel mai “bun” segment este cel care se sfârşeşte primul.

Restricţia R: Începutul segmentului care se adaugă trebuie să aibă abscisa mai mare decât sfârşitul oricărui dintre segmentele adăugate anterior în soluţie.

Structuri de date: fiecare segment va fi descris de un articol de 2 componente – valorile extremităţilor, iar setul de segmente – de un tablou de articole:

type segment = record st, dr : integer; end;

tablou = array [1..100] of segment;

Algoritm

1. Se sortează elementele din S după creşterea coordonatei extremităţii drepte.

s*1, s*2, …, s*N.

Se formează soluţia iniţială B, din primul element al şirului sortat (el nu poate încălca restricţia R)

k 1, Bk s*1.

2. Pentru fiecare i de la 2 la N se verifică condiţia:

Dacă s*i.st > bk.dr atunci

k k+1, Bk s*i

Date iniţiale

Datele se citesc din fişierul text data.in cu următoarea structură: prima linie a fişierului conţine un număr întreg N – numărul de segmente. Următoarele N linii conţin cîte 2 numere întregi, separate prin spaţiu – abscisa extremităţii stângi xi a segmentului i şi lungimea lui li.

Implementaretype segment=record st,dr : integer; end; sets = array[1..100] of segment;var a,b: sets; n,k: integer;

procedure readdata(var x: sets; var n: integer);var f: text; i,r: integer;begin assign(f, 'data.in'); reset(f); readln(f,n); for i:=1 to n do begin readln(f, x[i].st, r); x[i].dr:=x[i].st+r; end; close(f);end;

procedure sort (var x:sets; n:integer);var i,j: integer; t: segment;begin for i:=1 to n -1 do for j:=1 to n-i do if x[j].dr>x[j+1].dr then

begin t:=x[j]; x[j]:=x[j+1]; x[j+1]:=t; end;

end;

procedure solve(var y:sets; x:sets; n:integer; var k:integer);

var i: integer;begin y[1]:=x[1]; k:=1; for i:=2 to n do if x[i].st > y[k].dr then begin k:=k+1; y[k]:=x[i]; end;end;

procedure print(x: sets;k:integer);var i: integer; begin writeln(k); for i:=1 to k do writeln(x[i].st, ' ',x[i].dr); end;

begin readdata(a,n);

sort(a,n); solve(b,a,n,k); print(b,k);end.

Output >

Probleme tip

A.Plata unei sume cu un număr minim de bancnote de valori date.

 Fie dată suma S (S < 30000) şi o serie de N (N < 10) tipuri de valori distincte (fiecare valoare nu depăşeşte 1000) a bancnotelor din bancomat. Numărul de bancnote de fiecare tip se consideră infinit.

 

Scrieţi un program, care va determina modalitatea de plată a sumei S cu un număr minim de bancnote.

B.Plata unei sume cu un număr minim de bancnote

În condiţiile problemei precedente, numărul de bancnote de fiecare tip va fi limitat de valorile v1, v2, …vn.