Problem pakowania plecaka

Wprowadzenie

Problem pakowania plecaka (ang. Knapsack Problem) to jeden z najbardziej klasycznych problemów optymalizacyjnych w informatyce. Jest to problem NP-trudny, który ma szerokie zastosowanie w życiu codziennym - od planowania inwestycji, przez optymalizację zasobów, po problemy logistyczne.

Definicja problemu

Mamy: - Plecak o określonej pojemności (wagowej lub objętościowej) W - Zestaw przedmiotów n, gdzie każdy przedmiot i ma: - Wartość v[i] - jak cenny jest przedmiot - Wagę w[i] - ile waży przedmiot

Cel: Wybrać podzbiór przedmiotów o maksymalnej łącznej wartości, tak aby suma wag nie przekroczyła pojemności plecaka.

Maksymalizuj: Σ v[i] * x[i]
Przy ograniczeniu: Σ w[i] * x[i] ≤ W

gdzie x[i] określa, czy przedmiot i został wybrany.

Warianty problemu plecaka

1. Problem plecaka 0/1 (0/1 Knapsack)

Ograniczenie: Każdy przedmiot można wziąć tylko raz lub wcale.

x[i] ∈ {0, 1}

Przykład:

Pojemność plecaka: W = 10 kg
Przedmioty:
  Przedmiot 1: waga = 6 kg,  wartość = 30 zł
  Przedmiot 2: waga = 3 kg,  wartość = 14 zł
  Przedmiot 3: waga = 4 kg,  wartość = 16 zł
  Przedmiot 4: waga = 2 kg,  wartość = 9 zł

Rozwiązanie: Przedmioty 1, 3, 4 → waga = 12 kg (przekroczenie!)
Lepsze: Przedmioty 1, 2 → waga = 9 kg, wartość = 44 zł

Zastosowania: - Wybór inwestycji z ograniczonym budżetem - Ładowanie pojazdu z limitem ciężaru - Wybór zadań z ograniczonym czasem

2. Plecak ułamkowy (Fractional Knapsack)

Ograniczenie: Można wziąć część przedmiotu (liczby rzeczywiste).

x[i] ∈ [0, 1]

Przykład:

Pojemność plecaka: W = 10 kg
Przedmioty (jak wyżej)

Rozwiązanie zachłanne:
1. Sortuj po wartości/wagę (malejąco)
   - Przedmiot 1: 30/6 = 5.0 zł/kg
   - Przedmiot 3: 16/4 = 4.0 zł/kg
   - Przedmiot 2: 14/3 = 4.67 zł/kg
   - Przedmiot 4: 9/2 = 4.5 zł/kg

2. Bierz kolejno:
   - Przedmiot 1 (całość): 6 kg, wartość 30 zł
   - Przedmiot 2 (całość): 3 kg, wartość 14 zł
   - Przedmiot 4 (połowa): 1 kg, wartość 4.5 zł

Łącznie: 10 kg, wartość = 48.5 zł

Zastosowania: - Pakowanie materiałów sypkich (piasek, woda) - Optymalizacja portfela inwestycyjnego - Alokacja zasobów ciągłych

3. Plecak nieograniczony (Unbounded Knapsack)

Ograniczenie: Każdy przedmiot można wziąć dowolną liczbę razy.

x[i] ∈ {0, 1, 2, 3, ...}

Przykład:

Pojemność plecaka: W = 10 kg
Przedmioty:
  Przedmiot A: waga = 3 kg,  wartość = 15 zł
  Przedmiot B: waga = 4 kg,  wartość = 20 zł

Rozwiązanie:
- Można wziąć 3× przedmiot A (9 kg, 45 zł) + zostaje 1 kg
- Można wziąć 2× przedmiot B (8 kg, 40 zł) + zostaje 2 kg
- Można wziąć 1× B + 2× A (10 kg, 50 zł) ← OPTYMALNE

Zastosowania: - Problem wydawania reszty (monety) - Cięcie prętów na określone długości - Produkcja z wielokrotnym wykorzystaniem zasobów

Implementacje podstawowe

Problem 0/1 - Przegląd zupełny (brute force)

Wyjaśnienie bitmaski:

n = 4 przedmioty → 2^4 = 16 kombinacji

mask = 0b0000 → brak przedmiotów
mask = 0b0001 → przedmiot 0
mask = 0b0010 → przedmiot 1
mask = 0b0011 → przedmioty 0, 1
...
mask = 0b1111 → wszystkie przedmioty

Rekurencyjne podejście z backtrackingiem

Drzewo decyzji (dla powyższego przykładu):

                         KS(W=5, n=3)
                        /             \
                (bierzemy 3)        (pomijamy 3)
              KS(W=2, n=2)          KS(W=5, n=2)
              /         \            /          \
     (bierzemy 2)  (pomijamy 2)  (bierzemy 2) (pomijamy 2)
     KS(W=0,n=1)   KS(W=2,n=1)  KS(W=3,n=1)  KS(W=5,n=1)
          |            |            |            |
         ...          ...          ...          ...

Analiza złożoności różnych podejść

Porównanie metod

Przykładowe wyniki:

n=10, W=20:
{'Brute Force': {'time': 0.003s, 'value': 280},
 'Rekurencja': {'time': 0.002s, 'value': 280}}

n=15, W=30:
{'Brute Force': {'time': 0.095s, 'value': 420},
 'Rekurencja': {'time': 0.051s, 'value': 420}}

n=20, W=40:
{'Brute Force': {'time': 3.14s, 'value': 580},
 'Rekurencja': {'time': 1.82s, 'value': 580}}

Tabela złożoności czasowej

Metoda	Złożoność czasowa	Złożoność pamięciowa	Uwagi
Brute Force (bitmaska)	O(2^n · n)	O(n)	Sprawdza wszystkie kombinacje
Rekurencja (naiwna)	O(2^n)	O(n)	Stos wywołań rekurencyjnych
Rekurencja + memoizacja	O(n · W)	O(n · W)	Programowanie dynamiczne (top-down)
Tabulation (DP)	O(n · W)	O(n · W)	Programowanie dynamiczne (bottom-up)
DP optymalizacja pamięci	O(n · W)	O(W)	Używamy tylko 2 wierszy tablicy
Metoda zachłanna	O(n log n)	O(n)	Tylko dla plecaka ułamkowego!

Kiedy stosować którą metodę?

Decision Tree dla wyboru algorytmu

Praktyczne przykłady zastosowań

Przykład 1: Pakowanie bagażu

Przykładowe wyjście:

Optymalne pakowanie:
  - Laptop: 2 kg, wartość 1000 zł
  - Aparat: 1.5 kg, wartość 800 zł
  - Ubrania: 8 kg, wartość 200 zł
  - Buty: 3 kg, wartość 150 zł
  - Kosmetyki: 2 kg, wartość 80 zł

Łączna wartość: 2230 zł
Łączna waga: 16.5 kg
Pozostało: 3.5 kg

Przykład 2: Wybór projektów inwestycyjnych

Dlaczego problem plecaka jest NP-trudny?

Redukcja z problemu sumy podzbioru

Problem sumy podzbioru (Subset Sum):

Mając zbiór liczb S i wartość docelową T, czy istnieje podzbiór S' taki, że suma jego elementów równa się T?

Redukcja do problemu plecaka 0/1:

Ustaw:
- Wagi w[i] = wartości v[i] = elementy zbioru S
- Pojemność plecaka W = wartość docelowa T

Jeśli maksymalna wartość plecaka = T, to istnieje podzbiór o sumie T.

Kod weryfikacyjny:

Podsumowanie i porównanie wariantów

Cecha	Plecak 0/1	Plecak ułamkowy	Plecak nieograniczony
Definicja	Przedmiot cały lub wcale	Można brać ułamki	Przedmioty wielokrotnie
Zmienna decyzyjna	x[i] ∈	x[i] ∈ [0, 1]	x[i] ∈ ℕ
Złożoność	NP-trudny	P (wielomianowy)	NP-trudny
Najlepsza metoda	Programowanie dynamiczne	Algorytm zachłanny	Programowanie dynamiczne
Złożoność najlepszej	O(n·W)	O(n log n)	O(n·W)
Gwarancja optymalności	Tak (DP)	Tak (zachłanny)	Tak (DP)
Zastosowania	Wybór inwestycji, ładowanie	Alokacja zasobów ciągłych	Wydawanie reszty, cięcie

Kiedy używać programowania dynamicznego?

Charakterystyka problemu plecaka jako problemu DP

Problem plecaka ma dwie kluczowe cechy problemów DP:

Optymalna podstruktura:
Jeśli rozwiązanie dla plecaka o pojemności W i n przedmiotów jest optymalne, to dla mniejszego problemu (np. W-w[i] i n-1 przedmiotów) też jest optymalne.
Nakładające się podproblemy:
Rekurencyjnie rozwiązując problem, wielokrotnie obliczamy te same stany KS(W, n).

Wizualizacja nakładania się:

KS(W=10, n=4) wywołuje:
  - KS(W=7, n=3)
  - KS(W=10, n=3)

KS(W=10, n=3) wywołuje:
  - KS(W=6, n=2)  ← PONOWNIE obliczane!
  - KS(W=10, n=2)

KS(W=7, n=3) też wywołuje:
  - KS(W=6, n=2)  ← PONOWNIE obliczane!
  ...

Bez memoizacji: wykładnicza liczba obliczeń. Z memoizacją: O(n·W) unikalnych stanów.

Co dalej?

Po zrozumieniu analizy problemu plecaka, następne kroki to:

Lekcja 50: Plecak - metoda zachłanna
Algorytm zachłanny dla plecaka ułamkowego
Dlaczego zachłanny nie działa dla plecaka 0/1
Analiza kontrprzykładów
Lekcja 51: Plecak - programowanie dynamiczne
Implementacja algorytmu DP (tabulation i memoization)
Rekonstrukcja rozwiązania (które przedmioty wybrać)
Optymalizacja pamięci (z O(n·W) do O(W))
Lekcja 52: Najdłuższy wspólny podciąg (LCS)
Kolejny klasyczny problem DP
Zastosowania w porównywaniu tekstów i bioinformatyce
Lekcja 53: Najdłuższy rosnący podciąg (LIS)
Problem optymalizacji sekwencji
Rozwiązanie O(n²) i O(n log n)

Zadania praktyczne

Zadanie 1: Symulator planowania wycieczki

Napisz program, który pomoże zaplanować bagaż na wycieczkę, gdzie każdy przedmiot ma wagę, wartość użyteczności i kategorię (jedzenie, odzież, sprzęt). Maksymalna waga bagażu to 15 kg.

Zadanie 2: Problem cięcia pręta

Mamy pręt o długości L i cennik długości cięć. Znajdź optymalne cięcie maksymalizujące zysk. To jest wariant plecaka nieograniczonego.

Zadanie 3: Wizualizacja drzewa decyzji

Zaimplementuj funkcję rysującą drzewo decyzji dla małego problemu plecaka (n≤4), pokazując wszystkie rozważane kombinacje.

Następna lekcja: Plecak - metoda zachłanna (analiza kiedy działa i kiedy nie)