Plecak ze zoptymalizowanym zużyciem pamięci
Redukowanie dwóch wymiarów do jednego wiersza
Plecak ze zoptymalizowanym zużyciem pamięci to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 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.
Po co optymalizować pamięć
Pełna tabela wymaga pamięci rzędu n razy cap, co przy dużych danych może stać się problemem. Optymalizacja pamięci zmniejsza to zapotrzebowanie do jednego wielokrotnie używanego wiersza.
Liczy się tylko ostatni wiersz
Każda komórka odczytuje dane wyłącznie z poprzedniego wiersza, a nigdy ze starszych wierszy. Nie trzeba więc przechowywać całej tablicy naraz.
Zredukuj do jednej tablicy
Należy przechowywać jedną tablicę dp o długości cap+1. Podczas przetwarzania każdego przedmiotu jest ona nadpisywana w miejscu, aby reprezentować nowy wiersz.
dp = [0] * (cap + 1)Pułapka ponownego użycia
Jeśli pojemność jest przetwarzana od lewej do prawej, dp[w - wt[i]] może być już zaktualizowane dla tego samego przedmiotu. Pozwoliłoby to zabrać przedmiot i dwukrotnie.
Przetwarzaj pojemność wstecz
Rozwiązaniem jest przechodzenie po pojemnościach od największej do najmniejszej. Przejście wstecz gwarantuje, że dp[w - wt[i]] nadal zawiera wartość z poprzedniego wiersza.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Dlaczego przejście wstecz działa
Podczas obliczania dp[w] mniejszy indeks w - wt[i] pozostaje w tej iteracji niezmieniony, więc zgodnie z założeniem reprezentuje poprzedni wiersz.
Zatrzymaj się przy wt[i]
Pojemności mniejsze niż wt[i] nie pomieszczą przedmiotu, więc pętla kończy się na wt[i]. Pominięcie ich oszczędza kilka zbędnych operacji.
Pełna pętla
Całe rozwiązanie składa się z dwóch zagnieżdżonych pętli operujących na jednej tablicy. Najpierw przedmioty, a wewnątrz pojemność przetwarzana wstecz — wynik otrzymujemy bezpośrednio.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Odczytaj końcową komórkę
Po przetworzeniu wszystkich przedmiotów dp[cap] zawiera maksymalną wartość. Jest ona taka sama jak w tabeli 2D, ale wymaga znacznie mniej pamięci.
Ten sam czas, mniej pamięci
Algorytm nie stał się szybszy — nadal wykonuje pracę rzędu n razy cap. Zmniejszono jedynie pamięć z kwadratowej do liniowej.
Kiedy to się opłaca
Ta sztuczka pomaga, gdy cap jest duże, a tablica 2D przekroczyłaby limit pamięci. To podstawa zadań konkursowych, którą warto zapamiętać.
Szybkie sprawdzenie
Sprawdź najważniejszą zasadę plecaka 1D.
Podsumowanie
Zredukowali Państwo tabelę 2D do jednej tablicy i przetwarzali pojemność wstecz, aby zachować poprawność, zamieniając pamięć kwadratową na liniową. 🚀
Często zadawane pytania
Czy lekcja „Plecak ze zoptymalizowanym zużyciem pamięci” jest bezpłatna?
Tak — pełny tekst „Plecak ze zoptymalizowanym zużyciem 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 ze zoptymalizowanym zużyciem pamięci”?
Redukowanie dwóch wymiarów do jednego wiersza Ć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 2 z 4.
Ile czasu zajmuje lekcja „Plecak ze zoptymalizowanym zużyciem 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: wziąć czy zostawić
- Plecak ze zoptymalizowanym zużyciem pamięci
- Plecak bez ograniczeń i DP wydawania reszty
- Suma podzbioru i podział