WorksheetsMetoda Greedy - evaluare
Total questions: 11
Worksheet time: 40mins
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
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 (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:
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.
Denumirea metodei Greedy provine la cuvântul greedy care înseamnă
(a)
