Algorytm zachłanny jest poprawny, gdy problem ma własność greedy-choice oraz optimal substructure. Intuicyjnie da się to udowodnić argumentem wymiany: lokalnie najlepszy wybór można „wymienić” w rozwiązaniu optymalnym, więc lokalny wybór prowadzi do globalnego optimum.