4.1 Определение жадных алгоритмов
Жадные алгоритмы (Greedy Algorithms) — это класс алгоритмов, которые строят решение путем принятия локально оптимальных решений на каждом шагу. Эти решения принимаются на основе текущего состояния и не пересматриваются в будущем.
Жадные алгоритмы часто используются для решения задач оптимизации, где цель — максимизировать или минимизировать определенную величину.
Основные принципы жадных алгоритмов
- Жадный выбор: На каждом шагу алгоритм выбирает лучший локальный вариант, который, по его мнению, приведет к глобально оптимальному решению.
- Оптимальная подструктура: Проблема должна иметь свойство, что локально оптимальные решения могут быть объединены для получения глобально оптимального решения.
- Монотонность: После выбора очередного локально оптимального шага решение не должно быть ухудшено последующими выборами.
Преимущества и недостатки жадных алгоритмов
Преимущества:
- Простота реализации: Жадные алгоритмы часто просты для понимания и реализации.
- Эффективность: Обычно они работают быстрее, чем более сложные алгоритмы, такие как динамическое программирование.
Недостатки:
- Отсутствие глобальной оптимальности: Жадные алгоритмы не всегда приводят к глобально оптимальному решению.
- Не все задачи подходят: Только определенные задачи могут быть решены жадными алгоритмами.
Есть целый класс задач, у которых лучшее решение достигается жадным алгоритмом. Вам будет полезно узнать о таких.
4.2 Задача о размене монет
Задача:
У нас есть монеты разного номинала. Нужно найти минимальное количество монет для сдачи заданной суммы.
Решение:
Всегда берется монета с наибольшим номиналом, не превышающим оставшуюся сумму.
Временная сложность: O(n), где n — количество типов монет.
Пример кода на Python:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 Задача о рюкзаке
Задача:
У нас есть предметы с известной стоимостью и весом. Мы хотим положить в рюкзак фиксированного размера вещей на как можно большую сумму
В этом варианте задачи предметы можно делить на части. Например мы хотим купить разные крупы и можно хоть 1000 граммов, хоть 512.
Решение:
Сортировка предметов по удельной стоимости (стоимость/вес) и выбор наибольших удельных стоимостей до заполнения рюкзака.
Временная сложность: O(n log n), где n — количество предметов.
Пример кода на Python:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 Задача о покрытии отрезками
Задача:
Есть отрезки на прямой линии, заданные своими концами (x1, x2), и один целевой отрезок. Нужно найти минимальное количество отрезков, покрывающих все точки целевого отрезка.
Решение:
Сортировка отрезков по правому концу и выбор наименьшего отрезка, покрывающего текущую точку.
Временная сложность: O(n log n), где n — количество отрезков.
Пример кода на Python:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ