Metoda Greedy - evaluare

Dă exemple de probleme care se pot rezolva cu metoda Greedy

Metoda Greedy se aplică problemelor pentru care se dă o mulţime A cu n elemente şi pentru care trebuie determinată o submulţime a sa, S cu m elemente, care îndeplinesc anumite condiţii. (a)  

Ce deosebiri există între metoda greedy şi metoda backtracking

Metoda Greedy este o metodă de programare care:

Problema rucsacului

Se consideră un rucsac cu care se poate transporta o greutate maximă Gmax şi mai multe obiecte de greutăţi g1 , g2 ,…, gn , la transportul cărora se obţin câştigurile c1 , c2 ,…, cn . Se cere să se încarce rucsacul astfel încât să se obţină un câştig maxim.

Scrie pe scurt soluția( pașii de rezolvare) pentru problema discretă a rucsacului

Primul pas pentru rezolvarea problemei rucsacului, varianta discretă este să de determine (a)   fiecărui obiect în parte.

5 7

-2 -1 3 4 5

-5 -4 -1 2 5 7 8

Pentru datele de mai sus, se fac perechi din ambele mulțimi, alegând:

Problema rucsacului

- varianta discretă -

Problema spectacolelor

Într-o sală de spectacole, într-o zi, trebuie planificate n spectacole. Pentru fiecare spectacol se cunoaşte intervalul în care se desfăşoară. Se cere să se planifice un număr maxim de spectacole astfel încât să nu se suprapună.

Explică, pas cu pas, metoda de rezolvare.

Să se plătească o sumă s cu un număr minim de bancnote cu valori date. Se consideră că din fiecare tip de bancnotă se poate folosi un număr nelimitat de bancnote. În fișierul de intrare, pe rândul 1 este numărul de bancnote, pe rândul 2 suma iar pe rândul 3 tipul bancnotelor.

Scrie pașii de rezolvare.