Tehnica Greedy - Zataca A.

Extras din document

Tehnica Greedy. Problema banilor. Problema rucsacului. Variabile statice si variabile dinamice. Este foarte dificil de a scrie forma generală a unei probleme rezolva folosind tehnica Greedy. Să considerăm o mulţime A cu n elemente. Se cere o submulţime a sa cu m elemente (în cazul m=n este importantă ordinea alegerii elementelor), astfel încât să fie îndeplinite anumite condiţii (acestea diferă de la o problemă la alta). Exemplu: se consideră o mulţime de n numere reale. Se cere o submulţime a sa, astfel încât suma elementelor sale să fie maximă. Pentru rezolvare, vom alege un prim element al mulţimii de numere reale. Dacă este posibil, acesta va fi adăugat soluţiei, iniţial vide. Posibilitatea ca acesta să fie adăugat este dată de semnul numărului (acesta trebuie să fie mai mare ca O). Se alege un al doilea număr, cu care se procedează în mod asemănător. ...