|
Предыдущая часть: “Структуры данных: асимптотический анализ”
Алгоритм предназначен для достижения оптимального решения задачи. В подходе с жадным алгоритмом оно выбирается из заданной предметной области решений. Причём берутся ближайшие, кажущиеся оптимальными решения — отсюда и название «жадный».
В «жадных» алгоритмах ведётся поиск локально оптимального решения, которое в итоге может привести к нахождению глобально оптимальных решений, но обычно глобально оптимальными они не оказываются.
Подсчет монет
Цель этой задачи — досчитать до нужного значения, выбрав наименьшее количество монет. Согласно жадному подходу, в алгоритме выбирается наибольшая монета. Чтобы досчитать до 18 йен, имея монеты достоинством 1, 2, 5 и 10 йен, в жадном алгоритме проходится следующая последовательность шагов: | 
Главная 
