Plecak - programowanie dynamiczne

Wprowadzenie

W poprzednich lekcjach zobaczyliśmy, że algorytm zachłanny nie gwarantuje optymalnego rozwiązania dla problemu plecaka 0/1. Teraz poznamy programowanie dynamiczne - technikę, która zawsze znajduje optymalne rozwiązanie.

Kluczowa idea DP dla plecaka: - Rozwiązujemy mniejsze podproblemy: "Jaka jest maksymalna wartość dla plecaka o pojemności w używając pierwszych i przedmiotów?" - Budujemy rozwiązanie od dołu (tabulation) lub od góry z cache'owaniem (memoization) - Wykorzystujemy optymalną podstrukturę i nakładające się podproblemy

Podejście 1: Rekurencja z memoizacją (top-down)

Wzór rekurencyjny

Dla problemu plecaka 0/1 definiujemy:

dp[i][w] = maksymalna wartość dla plecaka o pojemności w
           używając pierwszych i przedmiotów

Wzór rekurencyjny:
dp[i][w] = max(
    dp[i-1][w],                          // NIE bierzemy przedmiotu i
    dp[i-1][w - weight[i]] + value[i]    // BIERZEMY przedmiot i
)

Warunki brzegowe:
dp[0][w] = 0  dla każdego w (brak przedmiotów → wartość 0)
dp[i][0] = 0  dla każdego i (pojemność 0 → wartość 0)

Decyzja: Dla każdego przedmiotu i możemy: 1. Pominąć go → wartość = dp[i-1][w] 2. Wziąć go (jeśli się mieści) → wartość = dp[i-1][w - weight[i]] + value[i]

Wybieramy maksimum z tych dwóch opcji.

Implementacja z memoizacją

Wyjaśnienie:

dp(2, 50) = max(
    dp(1, 50),           // Pomijamy przedmiot 2 (waga 30, wartość 120)
    dp(1, 20) + 120      // Bierzemy przedmiot 2
)

dp(1, 50) = max(
    dp(0, 50),           // Pomijamy przedmiot 1 (waga 20, wartość 100)
    dp(0, 30) + 100      // Bierzemy przedmiot 1
)

dp(1, 20) = max(
    dp(0, 20),           // Pomijamy przedmiot 1
    dp(0, 0) + 100       // Bierzemy przedmiot 1
)

...

Dzięki memoizacji, każdy stan (i, w) obliczamy tylko raz!

Podejście 2: Tabulation (bottom-up)

Implementacja tabelaryczna

Wizualizacja tablicy DP:

Przedmioty: [10kg/60zł, 20kg/100zł, 30kg/120zł]
W = 50 kg

        w=0  w=10  w=20  w=30  w=40  w=50
i=0      0    0     0     0     0     0
i=1      0   60    60    60    60    60    (przedmiot 0: 10kg, 60zł)
i=2      0   60   100   160   160   160    (przedmiot 1: 20kg, 100zł)
i=3      0   60   100   160   180   220    (przedmiot 2: 30kg, 120zł)
                                      ↑
                                 WYNIK

Krok po kroku dla dp[3][50]:
- Nie bierzemy przedmiotu 2: dp[2][50] = 160
- Bierzemy przedmiot 2: dp[2][50-30] + 120 = dp[2][20] + 120 = 100 + 120 = 220
- max(160, 220) = 220

Drukowanie tablicy DP (debugging)

Wyjście:

Tablica DP:
       w= 0 w= 1 w= 2 w= 3 w= 4 w= 5 w= 6 w= 7 w= 8
i= 0     0    0    0    0    0    0    0    0    0
i= 1     0    0    3    3    3    3    3    3    3
i= 2     0    0    3    4    4    7    7    7    7
i= 3     0    0    3    4    5    7    8    9    9
i= 4     0    0    3    4    5    7    8    9   10

Maksymalna wartość: 10

Rekonstrukcja rozwiązania: Które przedmioty wybrać?

Algorytm backtracingu

Po obliczeniu tablicy DP, możemy zrekonstruować które przedmioty zostały wybrane:

Wyjście:

Maksymalna wartość: 220
Wybrane przedmioty (indeksy): [1, 2]

Szczegóły:
  Przedmiot 1: waga=20, wartość=100
  Przedmiot 2: waga=30, wartość=120

Łączna waga: 50/50

Wyjaśnienie backtracingu:

Start: i=3, w=50, dp[3][50]=220

Krok 1:
  dp[3][50] = 220 ≠ dp[2][50] = 160 → przedmiot 2 WYBRANY
  Aktualizuj: i=2, w=50-30=20

Krok 2:
  dp[2][20] = 100 ≠ dp[1][20] = 60 → przedmiot 1 WYBRANY
  Aktualizuj: i=1, w=20-20=0

Krok 3:
  w=0 → STOP

Wybrane: [2, 1] → po odwróceniu: [1, 2]

Optymalizacja pamięci: O(n·W) → O(W)

Obserwacja

Zauważ, że przy obliczaniu dp[i][w] potrzebujemy tylko: - Bieżącego wiersza: dp[i][...] - Poprzedniego wiersza: dp[i-1][...]

Możemy użyć tylko jednej tablicy 1D zamiast 2D!

Implementacja z jedną tablicą

Wyjaśnienie iteracji od końca:

Przykład krok po kroku:

Przedmioty: [10kg/60zł, 20kg/100zł, 30kg/120zł]
W = 50

Inicjalizacja:
dp = [0, 0, 0, ..., 0]  (51 zer)

Po przedmiocie 0 (10kg, 60zł):
dp = [0, 0, ..., 0, 60, 60, 60, ..., 60]
           0-9      10  11  12      50

Po przedmiocie 1 (20kg, 100zł):
dp = [0, ..., 0, 60, ..., 60, 100, 160, 160, ..., 160]
      0-9       10      19   20   30   31       50

Po przedmiocie 2 (30kg, 120zł):
dp = [0, ..., 0, 60, ..., 100, 160, 180, 220, 220, ..., 220]
      0-9       10      20   30   40   50   51       50
                                       ↑
                                    WYNIK

Benchmark: Memoization vs Tabulation vs Optymalizacja

Przykładowe wyniki:

n=20, W=50:
  Memoization          → czas: 0.002134s, wartość: 412
  Tabulation           → czas: 0.001987s, wartość: 412
  Optymalizacja        → czas: 0.000891s, wartość: 412

n=50, W=100:
  Memoization          → czas: 0.012456s, wartość: 987
  Tabulation           → czas: 0.009823s, wartość: 987
  Optymalizacja        → czas: 0.004512s, wartość: 987

n=100, W=200:
  Memoization          → czas: 0.048723s, wartość: 1821
  Tabulation           → czas: 0.035647s, wartość: 1821
  Optymalizacja        → czas: 0.016234s, wartość: 1821

Obserwacje: - Optymalizacja najszybsza (mniej alokacji pamięci) - Tabulation szybsze niż memoization (mniej overhead funkcji) - Wszystkie mają tę samą złożoność O(n·W), ale stałe są różne

Porównanie: Zachłanny vs DP

Przykładowe wyjście:

Algorytm zachłanny:
  Wartość: 1542
  Czas: 0.000032s
  Optymalność: 87.3%

Programowanie dynamiczne:
  Wartość: 1767
  Czas: 0.004521s
  Optymalność: 100.0%

Różnica wartości: 225
Stosunek czasu DP/Zachłanny: 141.28x

Wnioski: - DP jest wolniejsze, ale zawsze optymalne - Zachłanny jest szybki, ale może być nieoptymalny (tutaj: 87.3%) - Wybór zależy od wymagań: szybkość vs dokładność

Wariant: Plecak nieograniczony (Unbounded Knapsack)

Dla plecaka nieograniczonego (każdy przedmiot można wziąć wielokrotnie), algorytm DP się zmienia:

Różnica między 0/1 a unbounded:

Praktyczne zastosowanie: System rekomendacji treści

Przykładowe wyjście:

Rekomendowane treści:
  - Film A: 90 min, engagement 85
  - Tutorial E: 25 min, engagement 50

Łączny engagement: 135
Łączny czas: 115 min (pozostało: 5 min)

Podsumowanie algorytmów plecaka

Algorytm	Typ problemu	Złożoność czasowa	Złożoność pamięciowa	Optymalność
Brute Force	0/1, Unbounded	O(2^n)	O(n)	✅ Tak
Rekurencja naiwna	0/1	O(2^n)	O(n)	✅ Tak
Memoization	0/1	O(n·W)	O(n·W)	✅ Tak
Tabulation	0/1	O(n·W)	O(n·W)	✅ Tak
DP optymalizacja	0/1	O(n·W)	O(W)	✅ Tak
Zachłanny	Fractional	O(n log n)	O(n)	✅ Tak
Zachłanny	0/1	O(n log n)	O(n)	❌ Nie (≥50%)
DP unbounded	Unbounded	O(n·W)	O(W)	✅ Tak

Co dalej?

Po opanowaniu problemu plecaka z programowaniem dynamicznym, następne kroki to:

Lekcja 52: Najdłuższy wspólny podciąg (LCS)
Kolejny klasyczny problem DP
Zastosowania: diff, plagiarism detection, bioinformatyka
Algorytm O(m·n) z optymalizacją pamięci
Lekcja 53: Najdłuższy rosnący podciąg (LIS)
Problem optymalizacji sekwencji
Rozwiązanie O(n²) i O(n log n)
Zastosowania: analiza danych czasowych
Inne problemy DP:
Najkrótsza ścieżka w grafie (Bellman-Ford, Floyd-Warshall)
Problem wydawania reszty (Coin Change)
Edycyjna odległość (Edit Distance)
Palindromy i inne problemy na stringach

Zadania praktyczne

Zadanie 1: Wizualizacja tablicy DP

Napisz funkcję, która rysuje tabelę DP krok po kroku, pokazując jak wypełniane są poszczególne komórki.

Zadanie 2: Multi-dimensional knapsack

Rozszerz problem plecaka o dwa ograniczenia (np. waga i objętość). Każdy przedmiot ma wagę, objętość i wartość.

Zadanie 3: Plecak z priorytetami

Dodaj priorytety do przedmiotów. Jeśli dwa rozwiązania mają tę samą wartość, wybierz to z wyższą sumą priorytetów.

Zadanie 4: Analiza wrażliwości

Dla danego rozwiązania optymalnego, sprawdź jak zmienia się wynik przy zmianie pojemności plecaka o ±10%.

Następna lekcja: Najdłuższy wspólny podciąg (LCS) - algorytm podobny do plecaka, ale dla stringów