Какво е жаден алгоритъм и как се прилага при решаване…

Жадният алгоритъм е хеуристичен подход, който на всеки етап взема локално оптимално решение, надявайки се, че това ще доведе до глобално оптимално решение.

Приложения:

Задача за избор на дейности (Activity Selection Problem):

Задача: Изберете максимално количество несъвпадащи по време интервали от даден набор.
Жадно решение: Подредете интервалите по нарастващия време на завършване. На всеки етап изберете интервал с най-малко време на завършване, който не се припокрива с вече избраните.

# Пример за избор на дейности
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Подреждане по време на завършване

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Задача за разпределяне на монети (Coin Change Problem) за канонични набори от монети:
- Задача: Издайте зададената сума с минимален брой монети.
- Жадно решение: Използвайте възможно най-големите номинали монети, докато сумата не бъде издадена. Работи само за определени набори от монети (например 1, 5, 10, 25).
```
# Пример за разпределяне на монети (за канонични монети)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Краскал алгоритъм за намиране на минимално разпределително дърво (Minimum Spanning Tree):
- Задача: Намерете подмножество ребра, което свързва всички върхове с минимално общо тегло на ребрата.
- Жадно решение: Подредете всички ребра по тегло във възходящ ред. Постепенно добавяйте ребра, ако не образуват цикъл с вече избраните, докато не свържете n-1 ребра (където n е броят на върховете).

Жадните алгоритми са лесни за реализиране, но не винаги намират глобално оптимално решение за произволни задачи. За някои задачи (например, задача за разпределяне на монети с произволен набор, задача за раница в общия случай) жадният подход не е оптимален. За гарантиране на оптималността или по-добра приближеност може да се наложи динамично програмиране или други методи. Преди прилагане на жаден алгоритъм трябва да се уверите, че той е подходящ за дадената задача.

Какво е жаден алгоритъм и как се прилага при решаване на задачи?