PL 
EnglishDomyślny
Українська🎒 Problem plecakowy 0/1
Zmaksymalizuj wartość, nie przekraczając pojemności. Obserwuj, jak programowanie dynamiczne wypełnia tablicę dp komórka po komórce rekurencją „brać czy pominąć”, a potem odtwarza optymalny zestaw przedmiotów — i zobacz, dlaczego metoda zachłanna zawodzi.
O problemie plecakowym 0/1
Problem plecakowy 0/1 to klasyczny problem optymalizacji kombinatorycznej: mając n przedmiotów, każdy o wadze wᵢ i wartości vᵢ, należy wybrać podzbiór maksymalizujący łączną wartość, nie przekraczając pojemności wagowej W. Oznaczenie „0/1” wskazuje, że każdy przedmiot musi zostać zabrany w całości albo wcale — wybór ułamkowy jest niedozwolony. Problem jest NP-trudny, co oznacza, że nie znamy algorytmu wielomianowego rozwiązującego wszystkie przypadki, ale podejście programowania dynamicznego (PD) działa w czasie pseudowielomianowym O(nW) i znajduje dokładne optimum.
W tej symulacji możesz dodawać, edytować lub usuwać przedmioty i obserwować, jak tabela PD wypełnia się komórka po komórce: każda komórka dp[i][w] przechowuje maksymalną wartość osiągalną przy użyciu pierwszych i przedmiotów i pojemności w. Po ukończeniu tabeli faza wstecznego śledzenia (backtracking) odtwarza optymalny wybór przedmiotów, podświetlony na siatce, a porównanie obok pokazuje, jak zachłanna heurystyka ułamkowa różni się od dokładnego rozwiązania PD.
Najczęściej zadawane pytania
Jaka jest relacja rekurencyjna dla programowania dynamicznego w problemie plecakowym 0/1?
dp[i][w] = max(dp[i−1][w], dp[i−1][w − wᵢ] + vᵢ), jeśli wᵢ ≤ w, w przeciwnym razie dp[i−1][w]. Pierwszy człon pomija przedmiot i; drugi go zabiera (możliwe tylko, gdy jego waga się mieści). Przypadek bazowy to dp[0][w] = 0 dla każdego w. Ostateczną odpowiedzią jest dp[n][W].
Dlaczego problem plecakowy 0/1 nazywany jest NP-trudnym?
NP-trudność oznacza, że nie znamy algorytmu wielomianowego rozwiązującego wszystkie przypadki. Podejście PD działa w czasie O(nW), ale samo W może być wykładniczo duże w swojej reprezentacji binarnej (pseudowielomianowe, nie prawdziwie wielomianowe). Problem został wykazany jako NP-zupełny przez redukcję z problemu sumy podzbioru przez Karpa w 1972 roku. W praktyce dla umiarkowanego W (do milionów) PD jest w pełni wykonalne.
Czym różni się zachłanny plecak ułamkowy od wersji 0/1?
Plecak ułamkowy pozwala dzielić przedmioty; zachłanna strategia zawsze wybierająca przedmiot o najwyższym stosunku wartości do wagi (vᵢ/wᵢ) daje rozwiązanie optymalne w czasie O(n log n). Dla plecaka 0/1 takie podejście zachłanne może zawieść: np. przy pojemności 10, przedmiotach (waga 6, wartość 6), (waga 5, wartość 5) i (waga 5, wartość 5), zachłanność wg stosunku wybiera przedmiot 1 dla wartości 6, ale zabranie przedmiotów 2 i 3 daje wartość 10.
Jak odzyskać optymalny zestaw przedmiotów po wypełnieniu tabeli PD?
Zaczynając od komórki dp[n][W], porównaj ją z dp[n−1][W]. Jeśli się różnią, przedmiot n został włączony; odejmij jego wagę od W i przejdź do wiersza n−1. Jeśli są równe, przedmiot n został pominięty; przejdź do dp[n−1][W]. Powtarzaj aż do wiersza 0. Ten przebieg wstecznego śledzenia działa w czasie O(n).
Czy złożoność pamięciową można zredukować poniżej O(nW)?
Tak. Ponieważ dp[i][w] zależy tylko od wiersza i−1, można użyć dwóch tablic jednowymiarowych o długości W+1 (bieżącej i poprzedniej), redukując pamięć do O(W). Jeśli iterujesz w od W w dół do wᵢ w pojedynczej tablicy 1D, możesz osiągnąć złożoność O(W) w miejscu, bez przechowywania poprzednich wierszy, choć wsteczne śledzenie wymaga wtedy ponownego obliczenia lub przechowywania różnic wierszy.
Czym jest podejście branch-and-bound (podziału i ograniczeń) do plecaka?
Branch-and-bound eksploruje wykładnicze drzewo decyzji uwzględnij/pomiń, ale przycina poddrzewa, których górne ograniczenie (zwykle relaksacja ułamkowa) nie może pobić bieżącego najlepszego rozwiązania. Dla wielu praktycznych przypadków jest to znacznie szybsze niż PD, gdy W jest ogromne, ale n małe. To podstawa komercyjnych solverów programowania całkowitoliczbowego, takich jak Gurobi i CPLEX.
Czy istnieją algorytmy aproksymacyjne dla problemu plecakowego?
Tak. Pełny wielomianowy schemat aproksymacji (FPTAS) daje rozwiązanie w granicach czynnika (1 − ε) od optimum w czasie O(n²/ε), poprzez skalowanie i zaokrąglanie wartości przedmiotów. Sprawia to, że tabela PD staje się na tyle mała, by obsłużyć duże W, gwarantując przy tym wyniki bliskie optymalnym — to fundamentalny wynik w teorii aproksymacji.
Jakie są praktyczne zastosowania problemu plecakowego?
Zastosowania obejmują załadunek ładunku (maksymalizacja przychodu przy ograniczeniach wagowych samolotu), alokację zasobów (przydzielanie CPU/pamięci konkurującym zadaniom), dobór portfela inwestycyjnego (maksymalizacja zwrotów przy ograniczeniu budżetowym), kryptografię (wczesne schematy klucza publicznego oparte na plecaku Merkle-Hellmana, obecnie złamane) oraz alokację rejestrów w kompilatorach.
Czym różni się wariant wielu plecaków?
W problemie wielu plecaków istnieje m plecaków, każdy o własnej pojemności, a przedmioty muszą być przydzielone do co najwyżej jednego plecaka. Uogólnia to problem pakowania do pojemników i jest ściśle trudniejsze; rozwiązania optymalne wymagają programowania liniowego całkowitoliczbowego lub heurystyk, takich jak first-fit-decreasing. Pojawia się w logistyce, pakowaniu maszyn wirtualnych w chmurze oraz problemach cięcia materiału.
Czym jest nieograniczony problem plecakowy?
W wariancie nieograniczonym każdy przedmiot może zostać wybrany dowolną liczbę razy (nieograniczona podaż). Relacja rekurencyjna zmienia się na dp[w] = max po wszystkich i, dla których wᵢ ≤ w, z (dp[w − wᵢ] + vᵢ), używając pojedynczej tablicy 1D iterowanej do przodu od w = 1 do W. Modeluje to scenariusze takie jak wydawanie reszty monetami czy cięcie pręta na kawałki w celu maksymalizacji zysku.