Plecak 0/1 i optymalizacja pamięci
Wyprowadzać rekurencję dla problemu plecakowego 0/1, wypełniać tablicę 2D, a następnie redukować ją do tablicy 1D przez iterowanie pojemności wstecz
Plecak 0/1 i optymalizacja pamięci to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem plecakowy 0/1
Problem 0/1 Knapsack: mając n przedmiotów, z których każdy ma wagę w[i] i wartość v[i], oraz plecak o pojemności W, należy wybrać przedmioty tak, aby zmaksymalizować łączną wartość bez przekraczania pojemności. Każdy przedmiot rozpatruje się dokładnie raz (0 = pomiń, 1 = wybierz). Jest to klasyczny przykład dużej rodziny rekrutacyjnych problemów DP, obejmującej między innymi partition-equal-subset-sum i target-sum.
Stan DP i zależność rekurencyjna
Zdefiniujmy dp[i][c] jako maksymalną wartość możliwą do uzyskania przy użyciu pierwszych i przedmiotów i pojemności c. Dla przedmiotu i mamy dwie możliwości: pominąć go (dp[i-1][c]) albo wybrać go, jeśli w[i] <= c (dp[i-1][c-w[i]] + v[i]). Zależność rekurencyjna ma postać: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]), gdy w[i] <= c; w przeciwnym razie dp[i][c] = dp[i-1][c]. Przypadek bazowy: dp[0][c] = 0 dla każdego c.
Implementacja tablicy DP 2D
Tablica 2D ma (n+1) x (W+1) wpisów i jest wypełniana wierszami, po jednym dla każdego przedmiotu. Po wypełnieniu wszystkich wierszy dp[n][W] zawiera maksymalną wartość. Algorytm działa w czasie O(n × W) i zużywa O(n × W) pamięci — jest to złożoność pseudowielomianowa, efektywna, gdy W jest niewielkie.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10Dlaczego w DP 1D pojemność iteruje się wstecz
Kluczowa obserwacja: wiersz i zależy wyłącznie od wiersza i-1. Możemy więc użyć pojedynczej tablicy 1D i aktualizować ją w miejscu. Jeśli jednak będziemy iterować pojemność c od lewej do prawej (od małych wartości do dużych), przedmiot i może zostać uwzględniony dwukrotnie — moglibyśmy użyć zaktualizowanej wartości dla c-w[i], która już zawiera przedmiot i. Iterowanie od prawej do lewej (od dużych wartości do małych) gwarantuje, że każdy przedmiot zostanie użyty najwyżej raz w ramach jednej aktualizacji wiersza.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowImplementacja 1D z optymalizacją pamięci
Przechowując tylko jedną tablicę i iterując pojemność od W do w[i], uzyskujemy taki sam wynik jak w tablicy 2D, używając O(W) pamięci. Złożoność czasowa pozostaje równa O(n × W). Tę optymalizację pamięci trzeba koniecznie zapamiętać — osoby prowadzące rozmowy rekrutacyjne często proszą o zredukowanie rozwiązania plecakowego 2D do 1D.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10Odtwarzanie wybranych przedmiotów
Aby ustalić, które przedmioty zostały wybrane, potrzebna jest pełna tablica 2D. Po jej wypełnieniu rozpocznij od dp[n][W] i prześledź tablicę wstecz: jeśli dp[i][c] != dp[i-1][c], przedmiot i został wybrany — odejmij jego wagę od c i przejdź do wiersza i-1. Kontynuuj aż do i = 0. Optymalizacja 1D pozbawia nas możliwości odtworzenia rozwiązania.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))Przykład praktyczny: maksymalizacja łącznej wartości
Rozważmy przedmioty: weights=[2,3,4,5], values=[3,4,5,6], W=8. Rozwiązanie optymalne: wybieramy przedmioty o wadze 3 (wartość 4) i wadze 5 (wartość 6) — łączna waga wynosi 8, a wartość 10. Możemy też wybrać przedmioty o wagach 2 i 5 — łączna wartość wyniesie 9, albo o wagach 2 i 3 — wartość wyniesie 7. DP poprawnie znajduje maksimum równe 10. Zauważmy, że podejście zachłanne (wybieranie przedmiotu o największym stosunku wartości do wagi) najpierw wybrałoby przedmiot o stosunku 1.5 (waga 2, wartość 3) — co nie zawsze prowadzi do rozwiązania optymalnego.
Plecak ułamkowy a plecak 0/1
W problemie Fractional Knapsack można wybierać ułamkowe części przedmiotów. Można go rozwiązać metodą zachłanną, sortując przedmioty według stosunku wartości do wagi. W problemie 0/1 Knapsack przedmioty są niepodzielne — metoda zachłanna zawodzi, dlatego potrzebne jest DP. Osoby prowadzące rozmowy rekrutacyjne wykorzystują tę różnicę, aby sprawdzić, czy wiedzą Państwo, kiedy można zastosować metodę zachłanną. Jeśli pytanie dotyczy wariantu ułamkowego, należy od razu wspomnieć o metodzie zachłannej z sortowaniem; w przypadku wariantu 0/1 należy zastosować DP.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))Złożoność czasowa pseudowielomianowa
Problem plecakowy 0/1 jest NP-zupełny, a mimo to rozwiązujemy go w czasie O(nW). Sprzeczność znika, gdy zauważymy, że O(nW) jest złożonością pseudowielomianową: W jest wartością, a nie rozmiarem danych wejściowych. Reprezentacja binarna W zajmuje O(log W) bitów, więc rzeczywista złożoność wynosi O(n × 2^(log W)), czyli jest wykładnicza względem rozmiaru danych wejściowych. Gdy W jest niewielkie (np. 10⁴), DP jest praktyczne; gdy W może wynosić 10⁹, potrzebne są inne podejścia.
Dopytanie rekrutera: duża pojemność
Jeśli rekruter narzuci bardzo dużą wartość W (np. 10⁹), ale n będzie niewielkie, standardowe DP przestanie działać. Możliwe alternatywy to: (1) meet-in-the-middle w czasie O(2^(n/2) × n), (2) przybliżenie zachłanne dla wariantu ułamkowego lub (3) branch-and-bound. W większości zadań rekrutacyjnych, w których W <= 10⁵, oczekiwanym rozwiązaniem jest DP 1D z iterowaniem wstecz.
Meet-in-the-middle dla dużej pojemności
Gdy W jest bardzo duże, ale n niewielkie (np. n=40), standardowe DP o złożoności O(nW) jest niewykonalne, a brute force o złożoności 2^n działa zbyt wolno. Metoda meet-in-the-middle dzieli przedmioty na dwie połowy, generuje wszystkie podzbiory 2^(n/2) dla każdej połowy, a następnie optymalnie łączy ich elementy. Jedną połowę należy posortować według wagi, a następnie dla każdego podzbioru drugiej połowy użyć wyszukiwania binarnego, aby znaleźć najlepsze połączenie mieszczące się w pojemności. Algorytm działa w O(2^(n/2) × n) — jest praktyczny dla n do 40.
Szybki test
Proszę sprawdzić swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: stan DP dla problemu plecakowego 0/1, dp[i][c], reprezentuje maksymalną wartość przy i przedmiotach i pojemności c, zależność rekurencyjna wybiera pominięcie albo wybranie każdego przedmiotu oraz optymalizacja pamięci do 1D iteruje pojemność od prawej do lewej, aby zapobiec wielokrotnemu zliczaniu przedmiotów. Następnie poznamy problem plecakowy nieograniczony, w którym przedmioty mogą być używane wielokrotnie, i zastosujemy go do problemu Coin Change II.
Często zadawane pytania
Czy lekcja „Plecak 0/1 i optymalizacja pamięci” jest bezpłatna?
Tak — pełny tekst „Plecak 0/1 i optymalizacja pamięci” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Plecak 0/1 i optymalizacja pamięci”?
Wyprowadzać rekurencję dla problemu plecakowego 0/1, wypełniać tablicę 2D, a następnie redukować ją do tablicy 1D przez iterowanie pojemności wstecz Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Plecak 0/1 i optymalizacja pamięci”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Plecak 0/1 i optymalizacja pamięci
- Plecak bez ograniczeń i Coin Change II
- Podział na równe sumy podzbiorów
- Suma docelowa ze znakami dodatnimi i ujemnymi