Жадный алгоритм - это алгоритм, который на каждом шаге выбирает оптимальный (в рамках текущего шага) вариант в рассчете на то, что конечное решение окажется оптимальным в глобальном смысле.
Небольшой пример:
Пусть у нас есть неограниченное количество монет разных номиналов и нам необходимо набрать сумму S. Рассмотрим два конкретных случая, каждый из которых попробуем решить жадным алгоритмом.
А именно будем действовать так: на каждом шаге будем брать монету, наибольшего номинала (оптимальный вариант внутри шага), который не превышает оставшуюся сумму.
a) Пусть номиналы монет равны 1, 5 и 10, а S = 27.
1) Берем 10, S: 27 -> 17
2) Берем 10, S: 17 -> 7
3) Берем 5, S: 7 -> 2
4) Берем 1, S: 2 -> 1
5) Берем 1, S: 1 -> 0
В итоге набрали сумму пятью монетами. Вы можете самостоятельно (например, перебором) убедиться в том, что за 4 монеты или меньше набрать 27 не получится.
б) Пусть номиналы монет равны 1, 5 и 7, а S = 24.
1) Берем 7, S: 24 -> 17
2) Берем 7, S: 17 -> 10
3) Берем 7, S: 10 -> 3
4) Берем 1, S: 3 -> 2
5) Берем 1, S: 2 -> 1
6) Берем 1, S: 1 -> 0.
Набрали сумму шестью монетами, но могли набрать S четырьмя монетами - две номиналом 7 и две номиналом 5.
Как видно из примера, не всегда задачи можно решить жадным алгоритмом. Но если он приводит к оптимальному ответу в целом, то обычно этот способ будет проще, чем использовать динамическое программирование или другие методы.