Plecak - metoda zachłanna

Wprowadzenie

Algorytmy zachłanne (ang. greedy algorithms) to strategia rozwiązywania problemów optymalizacyjnych, która na każdym kroku podejmuje lokalnie optymalną decyzję w nadziei, że doprowadzi to do globalnie optymalnego rozwiązania.

W kontekście problemu plecaka, metoda zachłanna polega na: 1. Wybieraniu przedmiotów według określonego kryterium (np. najwyższa wartość, najniższa waga, najwyższy stosunek wartość/waga) 2. Dodawaniu ich do plecaka dopóki się mieszczą 3. Zatrzymaniu gdy plecak jest pełny

Kluczowe pytanie: Czy ta strategia zawsze daje optymalne rozwiązanie?

Odpowiedź: Tak dla plecaka ułamkowego, NIE dla plecaka 0/1!

Algorytm zachłanny dla plecaka ułamkowego

Strategia: sortowanie po wartości/wagę

Dla plecaka ułamkowego (można brać części przedmiotów), algorytm zachłanny gwarantuje optymalne rozwiązanie:

Algorytm: 1. Oblicz wartość na jednostkę wagi dla każdego przedmiotu: ratio[i] = value[i] / weight[i] 2. Posortuj przedmioty malejąco według tego współczynnika 3. Bierz przedmioty w tej kolejności: - Jeśli przedmiot mieści się w całości → weź cały - Jeśli nie mieści się → weź tyle ile się zmieści (część ułamkową) 4. Stop gdy plecak pełny

Implementacja

Wyjaśnienie:

Przedmioty posortowane według ratio (wartość/waga):
1. Przedmiot 1: 100/20 = 5.0
2. Przedmiot 0: 60/10 = 6.0  ← NAJLEPSZY
3. Przedmiot 2: 120/30 = 4.0

Ale po sortowaniu malejąco:
1. Przedmiot 0: ratio = 6.0  → bierz całość (10 kg, 60 zł)
2. Przedmiot 1: ratio = 5.0  → bierz całość (20 kg, 100 zł)
3. Przedmiot 2: ratio = 4.0  → bierz całość (30 kg, 120 zł)

Suma: 60 kg > 50 kg

Poprawnie:
1. Przedmiot 0: całość → 10 kg, 60 zł (pozostało 40 kg)
2. Przedmiot 1: całość → 20 kg, 100 zł (pozostało 20 kg)
3. Przedmiot 2: 20/30 = 2/3 → 20 kg, 80 zł (pełny)

Łączna wartość: 60 + 100 + 80 = 240 zł

Dowód poprawności dla plecaka ułamkowego

Twierdzenie: Algorytm zachłanny daje optymalne rozwiązanie dla plecaka ułamkowego.

Dowód (przez wymianę): 1. Niech G będzie rozwiązaniem zachłannym (sortowanie po ratio) 2. Niech O będzie dowolnym rozwiązaniem optymalnym 3. Załóżmy, że G ≠ O

Znajdź pierwszy przedmiot i, który różni się w G i O:
W G: przedmiot i wzięty w większej ilości niż w O
W O: przedmiot j (j > i) wzięty w większej ilości
Ponieważ przedmioty są posortowane po ratio malejąco:
ratio[i] ≥ ratio[j]
Wymiana: Zamień część przedmiotu j w O na przedmiot i:
Wartość rośnie (bo ratio[i] ≥ ratio[j])
Waga pozostaje ta sama
Sprzeczność: O nie jest optymalne!
Zatem G = O, czyli algorytm zachłanny jest optymalny. ∎

Algorytm zachłanny dla plecaka 0/1 - BŁĄD!

Dlaczego zachłanny NIE działa dla plecaka 0/1?

Dla plecaka 0/1 (przedmioty tylko całkowicie), algorytm zachłanny NIE gwarantuje optymalnego rozwiązania.

Kontrprzykład:

Pojemność plecaka: W = 50 kg

Przedmioty:
  Przedmiot 0: waga = 10 kg,  wartość = 60 zł   → ratio = 6.0
  Przedmiot 1: waga = 20 kg,  wartość = 100 zł  → ratio = 5.0
  Przedmiot 2: waga = 30 kg,  wartość = 120 zł  → ratio = 4.0

Algorytm zachłanny (sortowanie po ratio): 1. Bierz przedmiot 0 (10 kg, 60 zł) → pozostało 40 kg 2. Bierz przedmiot 1 (20 kg, 100 zł) → pozostało 20 kg 3. NIE możemy wziąć przedmiotu 2 (30 kg > 20 kg)

Wynik zachłanny: wartość = 160 zł

Optymalne rozwiązanie: - Przedmiot 1 + Przedmiot 2 = 20 + 30 = 50 kg, wartość = 100 + 120 = 220 zł

Zachłanny dał 160 zł, optymalne to 220 zł → BŁĄD!

Implementacja zachłannego (błędna dla 0/1)

Wyjście:

Wynik zachłanny: 160 zł
Wybrane przedmioty: [0, 1]

Wynik optymalny: 220 zł
Wybrane przedmioty: [1, 2]

Różnica: 60 zł

Porównanie różnych strategii zachłannych

Dla plecaka 0/1 możemy próbować różnych kryteriów zachłannych:

Strategia 1: Najwyższa wartość

Kontrprzykład:

W = 10 kg

Przedmioty:
  0: waga = 9 kg,  wartość = 100 zł
  1: waga = 5 kg,  wartość = 60 zł
  2: waga = 5 kg,  wartość = 60 zł

Zachłanny (wartość): bierze 0 → 100 zł
Optymalny: bierze 1, 2 → 120 zł

BŁĄD!

Strategia 2: Najniższa waga

Kontrprzykład:

W = 10 kg

Przedmioty:
  0: waga = 1 kg,  wartość = 1 zł
  1: waga = 1 kg,  wartość = 1 zł
  ...
  9: waga = 1 kg,  wartość = 1 zł
  10: waga = 10 kg, wartość = 100 zł

Zachłanny (waga): bierze 0-9 → 10 zł
Optymalny: bierze 10 → 100 zł

BŁĄD!

Strategia 3: Najwyższy stosunek wartość/waga

To jest strategia używana w poprzednich przykładach. Już pokazaliśmy, że też nie działa dla plecaka 0/1.

Benchmark: Porównanie strategii zachłannych z optymalnym

Przykładowe wyniki:

=== Test 1: Kontrprzykład ===
Pojemność plecaka: 50
Przedmioty: 3

Optymalne                 → wartość:  220.0  (100.0% optymalnego)
Zachłanne (ratio)         → wartość:  160.0  ( 72.7% optymalnego)
Zachłanne (wartość)       → wartość:  220.0  (100.0% optymalnego)  ← SZCZĘŚCIE!
Zachłanne (waga)          → wartość:  160.0  ( 72.7% optymalnego)

=== Test 2: Losowe dane (n=8) ===
Pojemność plecaka: 50
Przedmioty: 8

Optymalne                 → wartość:  285.0  (100.0% optymalnego)
Zachłanne (ratio)         → wartość:  251.0  ( 88.1% optymalnego)
Zachłanne (wartość)       → wartość:  234.0  ( 82.1% optymalnego)
Zachłanne (waga)          → wartość:  198.0  ( 69.5% optymalnego)

=== Test 3: Losowe dane (n=12) ===
Pojemność plecaka: 40
Przedmioty: 12

Optymalne                 → wartość:  312.0  (100.0% optymalnego)
Zachłanne (ratio)         → wartość:  289.0  ( 92.6% optymalnego)
Zachłanne (wartość)       → wartość:  267.0  ( 85.6% optymalnego)
Zachłanne (waga)          → wartość:  241.0  ( 77.2% optymalnego)

Obserwacje: - Strategia ratio zazwyczaj najlepsza (ale nie zawsze!) - Czasami strategia wartość daje optymalne rozwiązanie (przez przypadek) - Strategia waga zazwyczaj najgorsza - Żadna strategia zachłanna nie gwarantuje optymalności dla plecaka 0/1

Aproksymacja: jak blisko optymalnego?

Współczynnik aproksymacji

Dla problemu plecaka 0/1, algorytm zachłanny (ratio) ma współczynnik aproksymacji = 2:

Wartość_zachłanna ≥ Wartość_optymalna / 2

Dowód (szkic): 1. Niech G = rozwiązanie zachłanne 2. Niech O = rozwiązanie optymalne 3. Niech i = pierwszy przedmiot nie wzięty przez algorytm zachłanny

Gdyby i mieścił się w plecaku, zachłanny by go wziął
Zatem i jest za ciężki → zabiera >50% pojemności
Wartość G zawiera wszystkie przedmioty przed i (o wyższym ratio)
W pesymistycznym przypadku, O zawiera tylko przedmiot i
Ale value[i] ≤ 2 × G (bo przedmioty przed i mają wyższe ratio)
Zatem G ≥ O / 2 ∎

Przykład pesymistycznego przypadku:

W = 10 kg

Przedmioty:
  0: waga = 1 kg,  wartość = 2 zł   → ratio = 2.0
  1: waga = 1 kg,  wartość = 2 zł   → ratio = 2.0
  ...
  4: waga = 1 kg,  wartość = 2 zł   → ratio = 2.0
  5: waga = 10 kg, wartość = 10 zł  → ratio = 1.0

Zachłanny: bierze 0-4 → 10 zł (5 przedmiotów po 2 zł)
Optymalny: bierze 5 → 10 zł

Współczynnik: 10 / 10 = 1.0 (równe!)

Ale modyfikacja:
  5: waga = 10 kg, wartość = 11 zł  → ratio = 1.1

Zachłanny: 10 zł
Optymalny: 11 zł
Współczynnik: 10 / 11 ≈ 0.91 ≈ 1/2 w granicy

Praktyczne zastosowania algorytmu zachłannego

Mimo że algorytm zachłanny nie jest optymalny dla plecaka 0/1, ma praktyczne zastosowania:

1. Szybkie przybliżenie

2. Górna granica dla DP

3. Heurystyka początkowa dla metaheurystyk

Algorytm zachłanny często używany jako punkt startowy dla algorytmów ewolucyjnych, symulowanego wyżarzania itp.

Kiedy używać algorytmu zachłannego?

Tabela decyzyjna

Typ problemu	Algorytm zachłanny	Powód
Plecak ułamkowy	✅ TAK - optymalny	Gwarantuje optymalne rozwiązanie
Plecak 0/1 (mały)	❌ NIE - użyj DP	Algorytm zachłanny nie jest optymalny
Plecak 0/1 (duży, >1000)	⚠️ MOŻE - aproksymacja	Szybkie przybliżenie (≥50% optymalnego)
Plecak nieograniczony	❌ NIE - użyj DP	Algorytm zachłanny nie jest optymalny
Górna granica	✅ TAK	Plecak ułamkowy jako upper bound
Punkt startowy dla metaheurystyk	✅ TAK	Dobra heurystyka początkowa

Podsumowanie: Zachłanny vs Optymalny

Porównanie algorytmów

Cecha	Algorytm zachłanny	Programowanie dynamiczne
Złożoność czasowa	O(n log n)	O(n·W)
Złożoność pamięciowa	O(n)	O(n·W) lub O(W)
Optymalność (plecak ułamkowy)	✅ Tak	✅ Tak
Optymalność (plecak 0/1)	❌ Nie	✅ Tak
Współczynnik aproksymacji (0/1)	≥ 50% optymalnego	100% (optymalny)
Implementacja	Bardzo prosta	Średnia
Zastosowania praktyczne	Ułamkowy, aproksymacja	Dokładne rozwiązania

Przykłady decyzji

Scenariusz 1: Planowanie cargo z płynami/gazami - Problem: Plecak ułamkowy - Rozwiązanie: Algorytm zachłanny - Powód: Optymalny i najszybszy

Scenariusz 2: Wybór 5 projektów z 10 dostępnych - Problem: Plecak 0/1, mały (n=10) - Rozwiązanie: Programowanie dynamiczne - Powód: Mały problem, potrzebujemy optymalnego rozwiązania

Scenariusz 3: Wybór 100 zadań z 10,000 dostępnych - Problem: Plecak 0/1, duży (n=10,000) - Rozwiązanie: Algorytm zachłanny (aproksymacja) - Powód: DP za wolne (O(n·W)), zachłanny da szybkie przybliżenie

Scenariusz 4: Planowanie inwestycji z dokładnym budżetem - Problem: Plecak 0/1, średni (n=50) - Rozwiązanie: Programowanie dynamiczne - Powód: Potrzebujemy optymalnego rozwiązania, n jest wystarczająco małe

Co dalej?

Po zrozumieniu metody zachłannej (i jej ograniczeń), następne kroki to:

Lekcja 51: Plecak - programowanie dynamiczne
Implementacja algorytmu DP (tabulation i memoization)
Gwarantowany optymalny wynik dla plecaka 0/1
Rekonstrukcja rozwiązania (które przedmioty wybrać)
Optymalizacja pamięci O(n·W) → O(W)
Porównanie: Algorytm zachłanny vs DP
Czas wykonania
Jakość rozwiązania
Kiedy który wybrać
Lekcja 52: Najdłuższy wspólny podciąg (LCS)
Kolejny klasyczny problem DP
Zastosowania: diff, plagiarism detection, bioinformatyka

Zadania praktyczne

Zadanie 1: Najgorszy przypadek

Znajdź przykład problemu plecaka 0/1, gdzie algorytm zachłanny (ratio) daje wynik dokładnie 50% optymalnego.

Zadanie 2: Hybrydowe podejście

Zaimplementuj algorytm, który: 1. Używa algorytmu zachłannego jako pierwszego przybliżenia 2. Następnie próbuje ulepszyć rozwiązanie przez lokalne przeszukiwanie (swap przedmiotów)

Zadanie 3: Wizualizacja

Stwórz wizualizację pokazującą, dlaczego algorytm zachłanny zawodzi dla plecaka 0/1 (np. wykres wartość vs waga dla wybranych przedmiotów).

Następna lekcja: Plecak - programowanie dynamiczne (algorytm optymalny dla plecaka 0/1)