Ce este un algoritm greedy și cum se aplică în…

Algoritmul greedy este o abordare heuristică care, în fiecare pas, ia decizia local optimă în speranța că aceasta va duce la o soluție global optimă.

Aplicații:

Problema selecției activităților:

Problema: Alegerea celui mai mare număr de intervale ne suprapuse dintr-un set dat.
Soluție greedy: Sortați intervalele după timpul de finalizare în ordine crescătoare. La fiecare pas, selectați intervalul cu cel mai mic timp de finalizare care nu se suprapune cu cele deja selectate.

# Exemplu de selecție a activităților
# 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]) # Sortare după timpul de finalizare

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) ]

Problema de schimbare a monedelor (Coin Change Problem) pentru seturi canonice de monede:
- Problema: Să se dea o sumă dată cu cel mai mic număr de monede.
- Soluție greedy: Folosiți numărul maxim posibil de cele mai mari denominații de monede până când suma este plătită. Funcționează doar pentru anumite seturi de monede (de exemplu, 1, 5, 10, 25).
```
# Exemplu de schimbare a monedelor (pentru monede canonice)
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}
```
Algoritmul lui Kruskal pentru găsirea arborelui de acoperire minimă:
- Problema: Găsiți o submulțime de muchii ale unui graf neorientat ponderat conex care leagă toate vârfurile cu suma minimă a greutăților.
- Soluție greedy: Sortează toate muchiile după greutate în ordine crescătoare. Adăugați muchii în ordine, dacă nu formează un ciclu cu cele deja selectate, până când se adaugă n-1 muchii (unde n este numărul de vârfuri).

Algoritmii greedy sunt ușor de implementat, dar nu găsesc întotdeauna soluția global optimă pentru probleme arbitrare. Pentru unele probleme (de exemplu, schimbarea monedelor cu seturi arbitrare, problema rucsacului în general), abordarea greedy nu este optimă. Pentru a garanta optimalitatea sau o aproximare mai bună, pot fi necesare metode precum programarea dinamică sau altele. Înainte de a aplica algoritmul greedy, trebuie să te asiguri că este potrivit pentru problema dată.

Ce este un algoritm greedy și cum se aplică în rezolvarea problemelor?