0/1-knapsack og pladseffektivisering
Udled rekurrensen for 0/1-knapsack, udfyld 2D-tabellen, og reducer derefter til et 1D-array ved at gennemløbe kapaciteten baglæns.
0/1-knapsack og pladseffektivisering er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
0/1-rygsækproblemet
0/1-rygsækproblemet: Givet n elementer, der hver har en vægt w[i] og en værdi v[i], samt en rygsæk med kapaciteten W, skal du vælge elementer for at maksimere den samlede værdi uden at overskride kapaciteten. Hvert element vælges præcis én gang (0 = spring over, 1 = vælg). Dette er prototypen på en stor familie af interviewopgaver om DP, herunder partition-equal-subset-sum og target-sum.
DP-tilstand og rekurrens
Definér dp[i][c] som den maksimale værdi ved at bruge de første i elementer med kapaciteten c. Der er to muligheder for element i: spring det over (dp[i-1][c]) eller vælg det, 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]. Basistilfælde: dp[0][c] = 0 for alle c.
Implementering af 2D-DP-tabellen
2D-tabellen har (n+1) x (W+1) poster og udfyldes række for række for hvert element. Når alle rækker er udfyldt, indeholder dp[n][W] den maksimale værdi. Det tager O(n × W) tid og kræver O(n × W) plads — en pseudopolynomiel kompleksitet, der er effektiv, når W er lille.
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 kapaciteten gennemløbes baglæns i 1D-DP
Den afgørende observation er: række i afhænger kun af række i-1. Derfor kan vi bruge et enkelt 1D-array og opdatere det på stedet. Hvis vi derimod gennemløber kapaciteten c fra venstre mod højre (lille til stor), kan element i blive talt to gange — vi kunne bruge den opdaterede værdi for c-w[i], som allerede indeholder element i. Ved at gennemløbe fra højre mod venstre (stor til lille) sikrer vi, at hvert element højst bruges én gang pr. rækkeopdatering.
# 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 rowPladsoptimeret implementering af 1D-DP
Ved kun at beholde ét array og gennemløbe kapaciteten fra W ned til w[i] opnår vi det samme resultat som med 2D-tabellen, men med O(W) plads. Tidskompleksiteten forbliver O(n × W). Denne pladsoptimering er vigtig at huske — interviewere beder ofte om at reducere 2D-rygsækken 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)) # 10Genskabelse af de valgte elementer
For at finde hvilke elementer der blev valgt, har du brug for hele 2D-tabellen. Når den er udfyldt, begynder du ved dp[n][W] og går baglæns: Hvis dp[i][c] != dp[i-1][c], blev element i taget med — træk dets vægt fra c, og gå til række i-1. Fortsæt, indtil i = 0. 1D-optimeringen fjerner muligheden for denne genskabelse.
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: Maksimér den samlede værdi
Overvej følgende elementer: weights=[2,3,4,5], values=[3,4,5,6], W=8. Den optimale løsning er at vælge elementerne med vægt 3 (værdi 4) og vægt 5 (værdi 6) — samlet vægt 8 og værdi 10. Du kan også vælge vægt 2 og 5 — samlet værdi 9 — eller vægt 2 og 3 — værdi 7. DP'en finder korrekt den maksimale værdi på 10. Bemærk, at den grådige tilgang (vælg det højeste værdi/vægt-forhold) først ville vælge elementet med forholdet 1.5 (vægt 2, værdi 3) — det er ikke altid optimalt.
Fraktioneret rygsæk kontra 0/1-rygsæk
I den fraktionerede rygsæk kan du tage brøkdele af elementer. Det kan løses grådigt ved at sortere efter værdi/vægt-forholdet. I 0/1-rygsækken kan elementerne ikke opdeles — den grådige metode fejler, og DP er nødvendig. Interviewere bruger denne forskel til at afprøve, om du ved, hvornår en grådig metode kan anvendes. Hvis du bliver spurgt om den fraktionerede variant, skal du straks nævne en grådig metode med sortering; hvis det er 0/1-varianten, skal du vælge 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))Pseudopolynomiel tidskompleksitet
0/1-rygsækproblemet er NP-komplet, og alligevel løser vi det på O(nW) tid. Modsigelsen løses, fordi O(nW) er pseudopolynomiel: W er en værdi, ikke inputstørrelsen. Den binære repræsentation af W kræver O(log W) bit, så den reelle kompleksitet er O(n × 2^(log W)), hvilket er eksponentielt i inputstørrelsen. Når W er lille (for eksempel 10⁴), er DP praktisk; når W kan være 10⁹, har vi brug for andre tilgange.
Opfølgende interviewspørgsmål: Stor kapacitet
Hvis intervieweren begrænser W til at være meget stor (for eksempel 10⁹), mens n er lille, bryder standard-DP'en sammen. Mulige alternativer er: (1) meet-in-the-middle på O(2^(n/2) × n) tid, (2) en grådig approksimation til den fraktionerede variant eller (3) branch-and-bound. I de fleste interviewopgaver med W <= 10⁵ er 1D-DP med baglæns gennemløb det forventede svar.
Meet-in-the-middle ved stor kapacitet
Når W er meget stor, men n er lille (for eksempel n=40), er standard-DP på O(nW) ikke mulig, mens en udtømmende gennemgang af 2^n muligheder er for langsom. Meet-in-the-middle opdeler elementerne i to halvdele, opregner alle 2^(n/2) delmængder for hver halvdel og kombinerer dem optimalt. Sortér den ene halvdel efter vægt, og brug derefter binær søgning for hver delmængde i den anden halvdel til at finde den bedste kombination inden for kapaciteten. Det tager O(2^(n/2) × n) tid — praktisk for n op til 40.
Hurtig kontrol
Kontrollér din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: tilstanden i 0/1-rygsæk-DP'en, dp[i][c], repræsenterer den maksimale værdi med i elementer og kapacitet c, rekurrensen vælger, om hvert element skal springes over eller tages med, og 1D-pladsoptimeringen gennemløber kapaciteten fra højre mod venstre for at forhindre, at elementer tælles to gange. Næste emne er den ubegrænsede rygsæk, hvor elementer kan genbruges, og hvor vi anvender den på Coin Change II.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “0/1-knapsack og pladseffektivisering” gratis?
Ja — hele teksten til “0/1-knapsack og pladseffektivisering” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “0/1-knapsack og pladseffektivisering”?
Udled rekurrensen for 0/1-knapsack, udfyld 2D-tabellen, og reducer derefter til et 1D-array ved at gennemløbe kapaciteten baglæns. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “0/1-knapsack og pladseffektivisering”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- 0/1-knapsack og pladseffektivisering
- Ubegrænset knapsack og Coin Change II
- Lige sum af delmængder
- Målsum med positive og negative fortegn