Plecak — gdy zachłanność zdradza

🎯 Po co Ci to?

Włamywacz staje przed sejfem pełnym kosztowności. Plecak uniesie 8 kg. Sztabka złota: 7 kg, warta 10 tys. Dwie srebrne: po 4 kg, warte po 6 tys. każda. Co zabrać? Zachłanny bierze złoto (najcenniejsze!) — i wychodzi z 10 tysiącami, zostawiając 12. Problem plecakowy to najsłynniejszy w informatyce przykład na to, jak lokalna łapczywość gubi globalny łup — i zarazem brama do programowania dynamicznego, które w następnej jednostce ten problem rozwiąże porządnie. Podstawa rozszerzona wymienia plecak z nazwy przy obu strategiach.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • sformułować problem plecakowy (dane, wynik, ograniczenie, cel);
  • pokazać na przykładach, że różne zachłanności (po wartości, po wadze, po opłacalności) zawodzą;
  • oszacować koszt sprawdzenia wszystkich możliwości i wyjaśnić, czemu potrzeba czegoś mądrzejszego.

📘 Wyjaśnienie

📐 DEFINICJA — problem plecakowy (dyskretny): danych jest $n$ przedmiotów, każdy z wagą i wartością, oraz udźwig plecaka $W$. Wybierz podzbiór przedmiotów o łącznej wadze $\le W$ i największej łącznej wartości. Przedmiotów nie wolno dzielić — bierzesz w całości albo wcale.

Po ludzku: co spakować, żeby unieść najwięcej wartości. Czym NIE jest: problemem „czy się zmieści" (to proste). Trudność siedzi w słowie najlepszy podzbiór — a podzbiorów jest $2^n$.

Trzy zachłanności — trzy porażki. Dla danych ze wstępu (udźwig 8; złoto 7 kg/10 tys.; srebro 4 kg/6 tys. ×2):

  • Po wartości (bierz najcenniejsze): złoto → 10 tys. Optimum: dwa srebra → 12 tys. ✗
  • Po wadze (bierz najlżejsze, zmieści się więcej): srebro, srebro → 12 tys. — tu akurat trafiła! Ale dla: udźwig 10, przedmioty {1 kg/1 zł ×9, 10 kg/50 zł} — bierze dziewięć drobiazgów (9 zł), a optimum to jedna ciężka rzecz (50 zł). ✗
  • Po opłacalności (wartość na kilogram — brzmi mądrze!): dla udźwigu 8 i {5 kg/25 zł (5 zł/kg), 4 kg/18 zł, 4 kg/18 zł (po 4,5 zł/kg)} bierze najpierw najopłacalniejszy 5-kilowy (zostają 3 kg — nic więcej nie wejdzie): 25 zł. Optimum: dwa po 4 kg = 36 zł. ✗

Każde kryterium ma swój kontrprzykład. To nie pech — to natura problemu: decyzja o jednym przedmiocie zmienia opłacalność wszystkich pozostałych (zajmuje miejsce!), a zachłanność z definicji tego sprzężenia nie widzi. Porównaj z resztą polskich nominałów (8.1), gdzie struktura była łaskawa — plecak łaskawy nie jest.

💭 Pomyśl: Skoro zachłanność zawodzi — sprawdźmy wszystkie możliwości. Ile podzbiorów trzeba przejrzeć dla 20 przedmiotów? A dla 60? (Podpowiedź z 2.7/6.5.)

Sprawdź odpowiedź

Każdy przedmiot: bierzesz albo nie — $2^{20} \approx 10^6$ podzbiorów (milion — komputer zdąży) i $2^{60} \approx 10^{18}$ (trylion — trzydzieści lat liczenia; klasa $O(2^n)$ z 6.5). Sprawdzanie wszystkiego działa dla zabawek i umiera dla rzeczywistości (magazyn ma tysiące pozycji). Zostajemy w potrzasku: zachłanność szybka-ale-błędna, pełny przegląd poprawny-ale-wieczny. Wyjście z potrzasku — następna jednostka. (Uczciwość każe dodać: sekret będzie działał, gdy udźwig jest rozsądną liczbą — plecak w pełnej ogólności pozostaje jednym z legendarnych twardych problemów informatyki.)

⚠️ Uwaga, pułapka

Istnieje wersja plecaka, w której zachłanność po opłacalności jest optymalna: plecak ciągły, gdzie przedmioty wolno dzielić (sypki towar: bierzesz 2,5 kg złotego piasku). Wtedy sypiesz najopłacalniejsze do pełna, potem następne — i to jest dowodliwie najlepsze. Morał podwójny: (1) drobna zmiana reguł (dzielić/nie dzielić) przenosi problem z „łatwych" do „twardych" — czytaj specyfikację jak prawnik; (2) na sprawdzianie „plecak" bez przymiotnika oznacza dyskretny — ten trudny.

🌍 Powiązania

Plecak to nie zabawka o złodzieju: załadunek kontenerowca i samolotu cargo (waga/wartość dosłownie), wybór projektów do budżetu (koszt/zysk przy limicie środków), przydział czasu antenowego reklamom, a nawet wybór pytań do nauki przed sprawdzianem przy limicie godzin (czas/punkty — Twój osobisty plecak). Wszędzie ta sama struktura: ograniczony zasób, niepodzielne kandydatury, maksymalizacja sumy. Rozpoznawanie plecaka w przebraniu to cenna umiejętność — bo od 8.3 będziesz umiał go rozwiązywać.

🛠️ Teraz Ty

Bez komputera: dla udźwigu 10 i przedmiotów A(6 kg/30 zł), B(5 kg/20 zł), C(5 kg/20 zł), D(1 kg/2 zł) rozegraj wszystkie trzy zachłanności i znajdź optimum ręcznie (podzbiorów sensownych jest mało). Z komputerem: napisz pełny przegląd (dla każdej liczby od 0 do $2^n - 1$ potraktuj bity jako decyzje bierz/nie bierz — dokładnie reprezentacja z działu 2!) i sprawdź nim swoje ręczne optimum; zmierz czas dla $n$ = 10, 20, 25.

📐 Definicje tej lekcji

  • Problem plecakowy — podzbiór przedmiotów o wadze $\le W$ i maksymalnej wartości; dyskretny (bez dzielenia) jest trudny, ciągły — zachłannie łatwy.
  • Pełny przegląd — sprawdzenie wszystkich $2^n$ podzbiorów; poprawny i wykładniczo beznadziejny.

📌 Najważniejsze w pigułce

  • Trzy naturalne zachłanności (wartość/waga/opłacalność) — każda ma kontrprzykład; sprzężenie „miejsce zajęte zmienia wszystko" jest niewidzialne dla łapczywości.
  • Pełny przegląd to $2^n$: milion dla 20 przedmiotów, wieczność dla 60.
  • Dzielenie przedmiotów zmienia ligę problemu — czytaj warunki zadania dosłownie.

🎒 Zadania

  1. Udźwig 7, przedmioty: {3 kg/9 zł, 3 kg/9 zł, 3 kg/9 zł, 6 kg/17 zł}. Rozegraj zachłanność po opłacalności i znajdź optimum. Co znowu poszło nie tak?
Wskazówka i odpowiedź

Opłacalności: 3 zł/kg dla trójek, ~2,83 dla szóstki — zachłanność bierze dwie trójki (6 kg, 18 zł), trzecia się nie mieści: 18 zł. Optimum… też 18 zł (dwie trójki)! Zachłanność akurat trafiła. To celowa złośliwość zadania: zachłanność czasem daje optimum nawet w plecaku — pojedynczy sukces niczego nie dowodzi. Dowód wymaga argumentu „zawsze", obalenie — jednego kontrprzykładu. Ta asymetria (z 1.2, z matematyki dowodów) obowiązuje w algorytmice bez taryfy ulgowej.

  1. Firma ma 100 tys. zł budżetu i projekty: A(40 tys./zysk 60), B(35 tys./50), C(30 tys./40), D(50 tys./65). Które wybierze zachłanność po zysku, a jaki jest wybór optymalny? Policz oba.
Wskazówka i odpowiedź

Po zysku: D(65, zostaje 50) → A(60, zostaje 10) → nic więcej: 125. Optimum: A+B+C zważą… 40+35+30 = 105 — za dużo! Sprawdź kombinacje: A+B = 75 tys./110; A+C = 70/100; B+C = 65/90; D+B = 85/115; D+C = 80/105; D+A = 90/125; trzech się nie da (najtańsze B+C+A=105 > 100). Optimum to D+A = 125 — zachłanność trafiła! A teraz zmień budżet na 105: wchodzą A+B+C = 150, a zachłanność dalej bierze D+A+… (zostaje 15, nic) = 125. Jedna zmiana parametru — i strategia z trafnej robi się stratna o 25 tysięcy. Tak wygląda „kruchość bez gwarancji" w pieniądzach.

  1. Sformułuj jako problem plecakowy: masz 90 minut na powtórkę przed sprawdzianem; tematy trwają (minuty/punkty): 30/8, 45/15, 20/6, 60/18, 15/4. Znajdź optimum dowolną metodą i porównaj z „uczę się po kolei od najkrótszego".
Wskazówka i odpowiedź

Udźwig 90, sześć… pięć przedmiotów. Po najkrótszym: 15+20+30 = 65 min (4+6+8 = 18 pkt), zostaje 25 — nic nie wchodzi: 18 pkt. Lepiej: 45+30+15 = 90 min → 15+8+4 = 27 pkt; albo 60+30 = 90 → 18+8 = 26; albo 60+20 = 80 → 24 (+nic za 10 min). Optimum: 27 pkt (45/30/15). Najkrótsze tematy skusiły liczbą, nie punktami — a Ty właśnie policzyłeś, że planowanie nauki to plecak i że intuicyjna strategia zostawiła jedną trzecią punktów na stole.

🔍 Sprawdź, czy umiesz

  • Sformułować plecak (dane/ograniczenie/cel) dla dowolnej historyjki.
  • Skonstruować kontrprzykład dla wskazanej zachłanności.
  • Oszacować $2^n$ i wskazać granicę wykonalności pełnego przeglądu.

Ucz się tej jednostki z asystentem