1. Wstęp – co znaczy być „zachłannym”?
Na co dzień „zachłanny” oznacza kogoś, kto chce wszystko od razu.
W informatyce to nie wada, tylko strategia.
Podejście zachłanne (ang. greedy approach) polega na tym, że w każdej chwili wybieramy najlepsze rozwiązanie lokalne, licząc na to, że doprowadzi nas ono do najlepszego rozwiązania ogólnego.
Czyli: nie myślę o całym planie, tylko o tym, co teraz da mi najwięcej zysku.
2. Przykłady z życia codziennego
Żeby to zrozumieć, nie trzeba znać żadnego języka programowania.
Wystarczy pomyśleć o codziennych sytuacjach.
Przykład 1: Wybieranie drogi do szkoły
Masz kilka ulic i skrzyżowań.
Zamiast sprawdzać wszystkie możliwe trasy (jak GPS z programowaniem dynamicznym), skręcasz zawsze tam, gdzie ruch wygląda najmniejszy.
To decyzja zachłanna – nie analizujesz całości, tylko reagujesz na bieżąco.
Przykład 2: Łapanie cukierków
Na stole masz rozsypane cukierki.
Nie planujesz, które zebrać – sięgasz po najbliższy.
To też zachłanność: bierzesz to, co w danej chwili wygląda najlepiej.
Przykład 3: Wydawanie reszty w sklepie
Masz wydać klientowi 47 zł.
Zaczynasz od największego możliwego nominału: 20 + 20 + 5 + 2.
Nie kombinujesz z innymi układami – zawsze wybierasz największy banknot, który „pasuje”.
To właśnie klasyczny algorytm zachłanny.
3. Idea podejścia zachłannego
Wybieraj najlepsze rozwiązanie lokalne, mając nadzieję, że doprowadzi cię do najlepszego rozwiązania globalnego.
Czyli krok po kroku:
- Masz problem do rozwiązania.
- Wybierasz najbardziej opłacalny ruch w danym momencie.
- Zmieniasz sytuację na prostszą (pozostały mniejszy problem).
- Powtarzasz decyzję, aż nie zostanie nic do rozwiązania.
Nie analizujesz wszystkiego – tylko to, co przed tobą.
4. Podejście zachłanne a inne metody
| Metoda | Jak działa | Przykład |
|---|---|---|
| Rekurencja | Dzieli problem na mniejsze części, rozwiązuje każdą osobno | Silnia, ciąg Fibonacciego |
| Programowanie dynamiczne | Zapamiętuje wcześniejsze wyniki, by nie liczyć ich ponownie | Najkrótsza ścieżka, plecak 0/1 |
| Podejście zachłanne | Wybiera najlepszy lokalny krok bez cofania się | Wydawanie reszty, wybór najkrótszego odcinka |
Zachłanność jest szybka, ale nie zawsze idealna — czasem „optymalne na teraz” nie znaczy „najlepsze na końcu”.
5. Klasyczny przykład – wydawanie reszty
Masz monety: 1, 2, 5, 10 zł.
Musisz wydać 47 zł, używając jak najmniejszej liczby monet.
Algorytm zachłanny:
zawsze wybierz największą monetę, która nie przekracza reszty.
def wydaj_reszte(kwota, monety):
wynik = []
for m in monety:
while kwota >= m:
kwota -= m
wynik.append(m)
return wynik
monety = [10, 5, 2, 1] # od największej do najmniejszej
print(wydaj_reszte(47, monety))
Wynik:
[10, 10, 10, 10, 5, 2]
Czyli 47 zł wydane za pomocą sześciu monet – bez planowania, po prostu zachłannie.
6. Drugi przykład – pakowanie plecaka (wersja zachłanna)
Masz plecak, który pomieści 10 kg.
Każdy przedmiot ma wagę i wartość.
Zachłanny algorytm wybierze te o największym stosunku wartości do wagi, aż zapełni plecak.
przedmioty = [
("złoto", 3, 100),
("srebro", 4, 60),
("miedz", 5, 40),
]
pojemnosc = 7
posortowane = sorted(przedmioty, key=lambda x: x[2]/x[1], reverse=True)
waga = 0
wartosc = 0
for nazwa, w, v in posortowane:
if waga + w <= pojemnosc:
waga += w
wartosc += v
print(f"Biorę {nazwa}")
print("Suma wartości:", wartosc)
Wynik:
Biorę złoto
Biorę srebro
Suma wartości: 160
Algorytm nie szuka idealnego układu – bierze to, co się opłaca w danej chwili.
7. Kiedy podejście zachłanne działa dobrze
Zachłanne rozwiązania dają dobry wynik wtedy, gdy problem ma tzw. „własność zachłanności” – czyli najlepszy lokalny krok prowadzi do najlepszego globalnego wyniku.
Przykłady, gdzie to działa:
- wydawanie reszty (jeśli nominały są dobrze dobrane),
- wybieranie najkrótszego połączenia w sieci (algorytm Kruskala, Prima),
- planowanie zadań z najkrótszym czasem wykonania.
Przykłady, gdzie to nie działa:
- problem plecakowy 0/1 (czasem warto zrezygnować z droższej rzeczy dla lepszego układu),
- niektóre labirynty (skręt w lewo nie zawsze skróci trasę).
8. Podejście zachłanne a człowiek
Człowiek też myśli zachłannie — często wybiera to, co daje natychmiastową nagrodę:
- idzie krótszą drogą, zamiast sprawdzić, czy tam są korki,
- kupuje coś na promocji, nie patrząc, czy naprawdę potrzebuje,
- wybiera najłatwiejsze rozwiązanie, zamiast długofalowo lepszego.
W programowaniu – tak jak w życiu – czasem to działa, a czasem nie.
9. Schemat myślenia zachłannego
START
↓
Wybierz to, co w danym momencie wygląda najlepiej
↓
Zaktualizuj dane (zmniejsz problem)
↓
Jeśli coś zostało do zrobienia → wróć do początku
↓
KONIEC
10. Zadania dla uczniów
Zadanie 1 – Wydaj resztę
Napisz program, który wydaje resztę zachłannie.
Użytkownik podaje kwotę, a program pokazuje, jakimi monetami ją wydać.
Spróbuj dodać nominał 3 zł i sprawdź, czy wynik nadal jest idealny.
Zadanie 2 – Zachłanne zbieranie punktów
Masz listę punktów w grze o różnych wartościach i czasie dotarcia.
Wybieraj zawsze ten punkt, który daje najwięcej punktów za sekundę.
Czy to zawsze najlepsza strategia?
Zadanie 3 – Porównanie metod
Weź problem „wydawania reszty” i rozwiąż go dwoma sposobami:
- zachłannie,
- wszystkimi możliwymi kombinacjami (np. pętlą lub rekurencją).
Porównaj wyniki i czas działania.
11. Podsumowanie
- Podejście zachłanne to sposób rozwiązywania problemów, w którym w każdej chwili wybieramy najlepszą lokalną opcję.
- Jest szybkie i proste, ale nie zawsze gwarantuje najlepszy wynik ogólny.
- Działa świetnie w problemach, gdzie najlepszy lokalny wybór naprawdę prowadzi do najlepszego globalnego.
- W życiu, matematyce i informatyce często trzeba wybrać między „mądrą zachłannością” a „cierpliwą analizą”.
12. Do zapamiętania
Zachłanny program nie planuje – reaguje.
Wybiera to, co wygląda najlepiej teraz, wierząc, że to doprowadzi go do celu.