Plecak 0/1: wziąć czy zostawić
Maksymalizowanie wartości przy ograniczeniu wagowym
Plecak 0/1: wziąć czy zostawić 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.
Historia problemu plecakowego
Mają Państwo plecak z ograniczeniem wagowym i stos przedmiotów. Problem plecakowy 0/1 pyta: które przedmioty maksymalizują wartość bez przekroczenia pojemności? 🎒
Weź albo pomiń
Określenie 0/1 oznacza, że każdy przedmiot jest albo w całości zabrany, albo całkowicie pominięty. Nie można zabrać połowy przedmiotu, więc każda decyzja sprowadza się do „tak” albo „nie”.
Dlaczego zachłanność zawodzi
Wybranie najtańszego albo najbardziej wartościowego przedmiotu jako pierwszego może zmarnować dostępną pojemność. Strategia zachłanna tutaj zawodzi, więc trzeba rozważyć rzeczywiste kombinacje.
Dwa wejścia
Dane są dwie równoległe listy: waga i wartość każdego przedmiotu, a także jedna pojemność. Przedmiot i ma wagę wt[i] i wartość val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Zdefiniuj stan
Niech dp[i][w] oznacza największą wartość, jaką można uzyskać za pomocą pierwszych i przedmiotów przy pojemności w. Precyzyjne nazwanie stanu jest kluczowe.
Decyzja o pominięciu
Jeśli pominięty zostanie przedmiot i, wartość pozostaje taka jak wcześniej: dp[i-1][w]. Dostępna pojemność nie zmienia się dla pozostałych przedmiotów.
Decyzja o zabraniu
Jeśli zabrany zostanie przedmiot i, należy dodać jego wartość i zmniejszyć pojemność: val[i] + dp[i-1][w - wt[i]]. Jest to możliwe tylko wtedy, gdy w jest co najmniej równe wt[i].
Wybierz lepszą gałąź
Rekurencja za pomocą max zachowuje po prostu większą z dwóch możliwości. Każda komórka korzysta z wyników obliczonych wcześniej.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])Wiersz bazowy
Przy zerowej liczbie przedmiotów można przenosić przedmioty o łącznej wartości zero przy dowolnej pojemności. Ten przypadek bazowy wypełnia pierwszy wiersz samymi zerami, na których można się oprzeć.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Wypełnij tabelę
Przedmioty należy przetwarzać w pętli zewnętrznej, a pojemności w wewnętrznej. Każda komórka odczytuje dane wyłącznie z wiersza powyżej, więc jeden przebieg wypełnia całą tabelę.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Odczytaj wynik
Prawa dolna komórka dp[n][cap] zawiera maksymalną wartość dla wszystkich przedmiotów i pełnej pojemności. Ta jedna komórka jest końcowym wynikiem.
Szybkie sprawdzenie
Sprawdź podstawową rekurencję problemu plecakowego 0/1.
Podsumowanie
Opanowali już Państwo problem plecakowy 0/1: każdy przedmiot należy zabrać albo pominąć, dp[i][w] przechowuje lepszą z opcji pominięcia i zabrania, a dp[n][cap] jest wynikiem. 🎉
Często zadawane pytania
Czy lekcja „Plecak 0/1: wziąć czy zostawić” jest bezpłatna?
Tak — pełny tekst „Plecak 0/1: wziąć czy zostawić” 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: wziąć czy zostawić”?
Maksymalizowanie wartości przy ograniczeniu wagowym Ć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: wziąć czy zostawić”?
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: wziąć czy zostawić
- Plecak ze zoptymalizowanym zużyciem pamięci
- Plecak bez ograniczeń i DP wydawania reszty
- Suma podzbioru i podział