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)  

• ADEVĂRAT
• FALS

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

• Tehnica Greedy nu dispune de mecanismele de întoarcere

• Tehnica backtracking ofera toate soluțiile posibile

• Tehnica Backtraking oferă posibilitatea de a găsi cea mai bună soluție din toate posibile

• Tehnica Backtracking dispune de mecanisme de a se merge înapoi (backtrack) și a se încearca o altă cale

Metoda Greedy este o metodă de programare care:

• furnizează toate soluțiile posibile

• se foloseşte în probleme de optimizare

• furnizează o singură soluţie (optimul global)

• soluția e obţinută prin alegeri succesive ale optimului local

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

• doar valorile pozitive

• doar valorile negative

• valorile ale căror produs este pozitiv

• toate valorile

Problema rucsacului

- varianta discretă -

• se adaugă obiecte tăiate

• se adaugă obiecte întregi

• se verifică la fiecare pas dacă s-a depășit Greutatea maximă admisă

• se poate rezolva optim cu ajutorul programării dinamice

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.