0/1 Knapsack og plassoptimalisering
Utled rekurrensen for 0/1-knapsack, fyll ut 2D-tabellen, og reduser den deretter til en 1D-tabell ved å iterere kapasiteten baklengs.
0/1 Knapsack og plassoptimalisering er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
0/1-ryggsekkproblemet
Problemet med 0/1-ryggsekken: Gitt n elementer, hvert med en vekt w[i] og en verdi v[i], samt en ryggsekk med kapasitet W, skal De velge elementer for å maksimere totalverdien uten å overskride kapasiteten. Hvert element kan tas med nøyaktig én gang (0 = hopp over, 1 = ta med). Dette er arketypen på en stor familie av intervjubaserte DP-problemer, blant annet partition-equal-subset-sum og target-sum.
DP-tilstand og rekurrens
Definer dp[i][c] som den maksimale verdien ved bruk av de første i elementene med kapasitet c. Det finnes to valg for element i: hopp over det (dp[i-1][c]) eller ta det med hvis w[i] <= c (dp[i-1][c-w[i]] + v[i]). Rekurrensen er: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) når w[i] <= c, ellers dp[i][c] = dp[i-1][c]. Grunntilfelle: dp[0][c] = 0 for alle c.
Implementering av 2D-DP-tabell
2D-tabellen har (n+1) x (W+1) oppføringer og fylles ut rad for rad for hvert element. Når alle radene er fylt ut, inneholder dp[n][W] den maksimale verdien. Dette kjører på O(n × W) tid og bruker O(n × W) plass — en pseudopolynomisk kompleksitet som er effektiv når W er liten.
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)) # 10Hvorfor kapasiteten itereres baklengs i 1D-DP
Den viktige observasjonen er at rad i bare avhenger av rad i-1. Derfor kan vi bruke én enkelt 1D-tabell og oppdatere den på stedet. Hvis vi derimot itererer over kapasiteten c fra venstre mot høyre (fra liten til stor), kan element i bli telt to ganger — vi kan bruke den oppdaterte verdien for c-w[i], som allerede inkluderer element i. Iterering fra høyre mot venstre (fra stor til liten) sikrer at hvert element brukes høyst én gang per radoppdatering.
# 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 rowPlassoptimalisert 1D-implementering
Ved å beholde bare én tabell og iterere over kapasiteten fra W ned til w[i] oppnår vi samme resultat som med 2D-tabellen, men med O(W) plass. Tidskompleksiteten forblir O(n × W). Denne plassoptimaliseringen er viktig å huske — intervjuere ber ofte kandidaten om å redusere 2D-ryggsekken til 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)) # 10Rekonstruksjon av de valgte elementene
For å finne hvilke elementer som ble valgt, trenger De hele 2D-tabellen. Når den er fylt ut, starter De ved dp[n][W] og går bakover: Hvis dp[i][c] != dp[i-1][c], ble element i tatt med — trekk vekten fra c og gå til rad i-1. Fortsett til i = 0. 1D-optimaliseringen forkaster muligheten til å rekonstruere løsningen.
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))Praktisk eksempel: Maksimer totalverdien
Vurder elementene: weights=[2,3,4,5], values=[3,4,5,6], W=8. Optimalt er å velge elementene med vekt 3 (verdi 4) og vekt 5 (verdi 6) — totalvekt 8 og verdi 10. De kan også velge vekt 2 og 5 — totalverdi 9. Eller vekt 2 og 3 — verdi 7. DP finner korrekt den maksimale verdien 10. Legg merke til at en grådig tilnærming (å velge det høyeste verdi/vekt-forholdet) først ville valgt elementet med forholdet 1.5 (vekt 2, verdi 3) — noe som ikke alltid er optimalt.
Fraksjonell ryggsekk kontra 0/1-ryggsekk
I det fraksjonelle ryggsekkproblemet kan De ta brøkdeler av elementer. Dette kan løses grådig ved å sortere etter verdi/vekt-forholdet. I 0/1-ryggsekkproblemet kan ikke elementene deles — en grådig tilnærming mislykkes, og DP er nødvendig. Intervjuere bruker dette skillet for å teste om De vet når en grådig tilnærming kan brukes. Hvis De blir spurt om den fraksjonelle varianten, bør De umiddelbart nevne grådig løsning med sortering; hvis det gjelder 0/1-varianten, bør De bruke 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))Pseudopolynomisk tidskompleksitet
0/1-ryggsekkproblemet er NP-komplett, men likevel løser vi det på O(nW) tid. Motsigelsen løses ved at O(nW) er pseudopolynomisk: W er en verdi, ikke størrelsen på inndataene. Den binære representasjonen av W krever O(log W) biter, så den faktiske kompleksiteten er O(n × 2^(log W)), som er eksponentiell i inndatastørrelsen. Når W er liten (for eksempel 10⁴), er DP praktisk; når W kan være 10⁹, trenger vi andre tilnærminger.
Oppfølgingsspørsmål fra intervjueren: Stor kapasitet
Hvis intervjueren setter W til å være svært stor (for eksempel 10⁹), mens n er liten, bryter standard-DP sammen. Alternativer er blant annet: (1) meet-in-the-middle med tidskompleksitet O(2^(n/2) × n), (2) en grådig approksimasjon for den fraksjonelle varianten eller (3) branch-and-bound. For de fleste intervjuproblemer med W <= 10⁵ er 1D-DP med iterering baklengs det forventede svaret.
Meet-in-the-middle ved stor kapasitet
Når W er svært stor, men n er liten (for eksempel n=40), er standard-DP med O(nW) urealistisk, mens brute-force med 2^n går for tregt. Meet-in-the-middle deler elementene i to halvdeler, enumererer alle 2^(n/2) delmengder for hver halvdel og kobler dem optimalt sammen. Sorter den ene halvdelen etter vekt, og bruk deretter binærsøk for hver delmengde i den andre halvdelen til å finne den beste sammenkoblingen innenfor kapasiteten. Dette kjører på O(2^(n/2) × n) — praktisk for n opptil 40.
Hurtigsjekk
Test Deres forståelse av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: 0/1-ryggsekk-DP har tilstanden dp[i][c], som representerer den maksimale verdien med i elementer og kapasitet c, rekurrensen velger om hvert element skal hoppes over eller tas med, og 1D-plassoptimaliseringen itererer over kapasiteten fra høyre mot venstre for å forhindre dobbelttelling av elementer. Deretter utforsker vi ubegrenset ryggsekk, der elementer kan brukes på nytt, og bruker dette på Coin Change II.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «0/1 Knapsack og plassoptimalisering» gratis?
Ja – hele teksten i «0/1 Knapsack og plassoptimalisering» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «0/1 Knapsack og plassoptimalisering»?
Utled rekurrensen for 0/1-knapsack, fyll ut 2D-tabellen, og reduser den deretter til en 1D-tabell ved å iterere kapasiteten baklengs. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «0/1 Knapsack og plassoptimalisering»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- 0/1 Knapsack og plassoptimalisering
- Ubegrenset knapsack og Coin Change II
- Lik sum for delmengder
- Målsum med positive og negative fortegn