Vom considera ca soluția optimă s* este cea pentru care o anumită funcție obiectiv f(s*) are valoarea maximă sau valoarea minimă. De exemplu, se cere să se determine soluția pentru care eficiența este maximă, sau pentru care costul este minim.
Problemele de optimizare se împart în două mari categorii:
a) probleme continue, în care s ia valori într-un
domeniu continuu;
b) probleme de optimizare discretă, în care s aparține
unei mulțimi discrete S={s1 , s2 , ...}.
În numeroase situații practice, mulțimea S a soluțiilor posibile este nu numai discretă, dar și finită S={s1 , s2 , ..., sn}. În astfel de situații, în principiu, pentru determinarea soluției optime se poate aplica tehnica "forței brute": se determină mai întâi toate soluțiile, se calculează pentru fiecare valoarea corespunzătoare a funcției obiectiv f și se alege soluția cu valoarea optimă (maximă sau minimă, după caz) a acestei funcții. Totuși, în numeroase cazuri, chiar dacă numărul de soluții posibile este finit, el este foarte mare. În astfel de cazuri, determinarea tuturor soluțiilor ar necesita un timp foarte mare de calcul, astfel încât aplicarea practică a tehnicii "forței brute" nu este rațională sau este chiar imposibilă. Din această cauză, au fost create diverse tehnici de determinare a soluției optime fară a fi necesară parcurgerea tuturor soluțiilor posibile.
În acest capitol se prezintă două dintre metodele de determinare a soluției pentru probleme de optimizare discretă: metoda Greedy și metoda programării dinamice.