Жадный алгоритм — это алгоритм, который на каждом этапе пытается принять самые оптимальные решения, считая, что в совокупности они дадут для задачи наилучшее решение. Эта формулировка чем-то перекликается с описанием алгоритмов «Разделяй и властвуй». Но в отличие от них, жадные алгоритмы не делят задачи на более мелкие, а решают исходную задачу итеративно.

Подсчёт сдачи

Подсчёт сдачи — это одна из самых распространённых задач из реальной жизни, решаемых жадно. Когда вы покупаете что-то за 247 рублей и протягиваете 500, продавцы не отдают вам 253 рубля сдачи монетками по одному рублю. Этих монет у них ограниченное множество, и в какой-то момент мелочи может просто не хватить. Перебирать в голове бессчётное множество различных комбинаций сдачи они тоже не будут. Вместо этого они берут максимальное количество банкнот или монет самого крупного номинала, потом номинала поменьше и так далее, пока не насчитают нужное количество рублей.

Например, чтобы отдать девять рублей, мы сначала берём максимальное количество монет самого большого номинала — одну пятирублевую. Затем максимальное количество монет поменьше — две по два рубля. Получилось всего три монеты — минимальное количество, которое нужно отдать.

Давайте посмотрим в следующих демонстрациях на другие примеры жадных алгоритмов, чтобы закрепить понимание концепта.