Что такое жадный алгоритм и как он применяется при решении задач?

Жадный алгоритм — эвристический подход, который на каждом шаге принимает локально оптимальное решение в надежде, что это приведет к глобально оптимальному решению.

Применение:

1. Задача о выборе деятельности (Activity Selection Problem):

   • Задача: Выбрать максимальное количество непересекающихся по времени интервалов из заданного набора.
   • Жадное решение: Сортировать интервалы по возрастанию времени окончания. На каждом шаге выбирать интервал с наименьшим временем окончания, который не пересекается с уже выбранными.

   python

2. Задача о сдаче мелочи (Coin Change Problem) для канонических наборов монет:

   • Задача: Выдать заданную сумму минимальным количеством монет.
   • Жадное решение: Использовать максимально возможное количество самых больших номи