Dataczwartek, 13 sierpnia 2026 Czas19:10:25
← Algorytmy i złożoność

Lekcja 7. Podejście zachłanne — jak wybierać najlepszy krok tu i teraz

Średni

Po co się tego uczymy?

Nie każdy problem trzeba rozwiązywać, analizując WSZYSTKIE możliwości — czasem szybsza i prostsza strategia "wybierz to, co teraz wygląda najlepiej" daje bardzo dobre (a czasem najlepsze) wyniki. Zrozumienie, KIEDY takie podejście działa, a kiedy zawodzi, jest kluczowe na maturze rozszerzonej z informatyki.

Teoria

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ślisz o całym planie, tylko o tym, co TERAZ da najwięcej zysku.

Idea krok po kroku: (1) masz problem do rozwiązania, (2) wybierasz najbardziej opłacalny ruch w danym momencie, (3) zmieniasz sytuację na prostszą (pozostały mniejszy problem), (4) powtarzasz decyzję, aż nie zostanie nic do rozwiązania. NIE analizujesz wszystkiego — tylko to, co przed tobą.

Porównanie z innymi strategiami poznanymi w tym dziale:

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".

Kiedy podejście zachłanne działa DOBRZE — gdy problem ma tzw. "własność zachłanności": najlepszy lokalny krok prowadzi do najlepszego globalnego wyniku. Przykłady: wydawanie reszty (jeśli nominały są dobrze dobrane), wybieranie najkrótszego połączenia w sieci (algorytmy Kruskala, Prima), planowanie zadań z najkrótszym czasem wykonania.

Kiedy NIE działa — problem plecakowy 0/1 (czasem warto ZREZYGNOWAĆ z pozornie droższej rzeczy dla lepszego układu), niektóre labirynty (skręt w lewo nie zawsze skróci trasę).

Podejście zachłanne a człowiek — ludzie też często myślą zachłannie: wybierają krótszą drogę bez sprawdzenia korków, kupują coś na promocji bez zastanowienia, wybierają najłatwiejsze rozwiązanie zamiast długofalowo lepszego. W programowaniu — tak jak w życiu — czasem to działa, a czasem nie.

Schemat

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

WYDAWANIE RESZTY (47 zł, monety 10/5/2/1):
47 → weź 10 → 37 → weź 10 → 27 → weź 10 → 17 → weź 10 → 7 → weź 5 → 2 → weź 2 → 0
Wynik: [10, 10, 10, 10, 5, 2]  (6 monet)

Przykład z życia

Sprzedawca w sklepie wydający resztę zawsze sięga po NAJWIĘKSZY pasujący nominał (najpierw banknoty 20 zł, potem 10 zł, potem monety) — nie zastanawia się nad WSZYSTKIMI możliwymi kombinacjami monet, tylko podejmuje najlepszą decyzję w danej chwili. To dokładnie algorytm zachłanny działający w codziennym życiu, milion razy dziennie w kasach na całym świecie.

wydaj_reszte.py

# Wydawanie reszty - klasyczny przykład algorytmu zachłannego
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]  (6 monet, bez planowania - po prostu zachłannie)

plecak_zachlanny.py

# Pakowanie plecaka (wersja zachłanna) - wybiera przedmioty o
# największym stosunku wartość/waga, aż zapełni dostępną pojemność
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

Komentarz i wyjaśnienie kodu

W wydaj_reszte() pętla for m in monety zakłada, że lista monet jest posortowana MALEJĄCO — to warunek konieczny strategii zachłannej: musimy zawsze próbować NAJPIERW największy możliwy nominał.

W przykładzie z plecakiem key=lambda x: x[2]/x[1] sortuje przedmioty według stosunku WARTOŚĆ/WAGA (od najlepszego) — algorytm bierze najpierw przedmiot o najlepszym "zysku na kilogram", a nie po prostu najdroższy czy najlżejszy. To pokazuje, że "zachłanność" nie zawsze oznacza "bierz największą wartość" — czasem trzeba przemyśleć, jaka WŁAŚCIWOŚĆ najlepiej definiuje "lokalnie najlepszy wybór".

Ćwiczenie samodzielne

Uruchom wydaj_reszte() dla kilku różnych kwot i sprawdź, czy wynik zawsze wygląda "sensownie" (najmniejsza możliwa liczba monet). Następnie dodaj do listy przedmioty czwarty przedmiot i sprawdź, jak zmienia się wynik pakowania plecaka.

Zadania do pracy własnej

  1. 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ł do listy monet i sprawdź, czy wynik nadal jest "idealny" (najmniejsza możliwa liczba monet).

  2. Masz listę punktów w grze o różnych wartościach i czasie dotarcia do nich. Napisz algorytm zachłanny, który zawsze wybiera punkt dający najwięcej "wartości na sekundę". Zastanów się: czy to ZAWSZE jest najlepsza strategia zbierania punktów?

  3. Weź problem "wydawania reszty" i rozwiąż go DWOMA sposobami: zachłannie (jak w przykładzie) oraz sprawdzając WSZYSTKIE możliwe kombinacje monet (pętlą lub rekurencją, szukając kombinacji o najmniejszej liczbie monet). Porównaj wyniki i czas działania obu metod — czy dla nominałów [10, 5, 2, 1] podejście zachłanne zawsze daje optymalny wynik? A co, gdyby dodać nominał 4 zł?

Typowe błędy

Zakładanie, że podejście zachłanne ZAWSZE daje optymalny wynik — to prawda TYLKO dla problemów mających "własność zachłanności" (jak dobrze dobrane nominały monet); dla problemu plecakowego 0/1 (gdzie NIE można wziąć części przedmiotu) zachłanność może dać wynik gorszy niż optymalny.

Zapominanie o posortowaniu danych przed zastosowaniem strategii zachłannej — bez posortowania monet malejąco albo przedmiotów wg stosunku wartość/waga, algorytm przestaje działać poprawnie.

Mylenie "algorytmu zachłannego" z "błędnym rozwiązaniem" — zachłanność to ŚWIADOMY kompromis między szybkością a gwarancją optymalności, nie błąd projektowy.

Nawiązanie do egzaminu zawodowego

Podejście zachłanne to trzecia (obok rekurencji i metody połowienia) uniwersalna strategia rozwiązywania problemów poznana w tym dziale. W kolejnej lekcji poznasz programowanie dynamiczne — strategię, która ROZWIĄZUJE problemy, gdzie zachłanność ZAWODZI (jak problem plecakowy 0/1), przez inteligentne zapamiętywanie wyników pośrednich.