Ubegrænset knapsack og Coin Change II

I den ubegrænsede rygsæk kan hvert element vælges et vilkårligt antal gange (i modsætning til 0/1-rygsækken, hvor hvert element højst bruges én gang). Definitionen af tilstanden er den samme — dp[c] = den maksimale værdi, der kan opnås med kapaciteten c — men gennemløbsretningen ændres. Fordi elementerne kan genbruges, vil vi tillade, at det aktuelle element bruges igen, når vi opdaterer dp[c], så vi gennemløber kapaciteten fra venstre mod højre (fremad).

Husk, at vi i 0/1-rygsækken gennemløb fra højre mod venstre for at forhindre genbrug. I den ubegrænsede rygsæk gør vi det modsatte: Vi gennemløber fra venstre mod højre. Når vi beregner dp[c], er dp[c-w] allerede blevet opdateret i det aktuelle gennemløb — det betyder, at element i muligvis allerede er taget med. Det er præcis det, vi ønsker: Element i kan føjes til igen i en løsning, der allerede indeholder element i.

Coin Change II spørger: Givet møntværdier og et beløb, hvor mange forskellige måder er der til at danne beløbet (hver mønt kan bruges et ubegrænset antal gange)? Dette er en variant af den ubegrænsede rygsæk, hvor vi i stedet for at maksimere en værdi tæller kombinationer. Definér dp[c] som antallet af måder at danne beløbet c på. Basistilfælde: dp[0] = 1 (én måde at danne 0 på: vælg ingenting).

For hver mønt gennemløber du beløbene fra venstre mod højre og akkumulerer: dp[c] += dp[c - coin]. Basistilfældet dp[0] = 1 starter optællingen. Bemærk, at den ydre løkke går over mønter, mens den indre løkke går over beløb — det giver naturligt kombinationstællinger (ikke permutationer), fordi hver møntværdi behandles præcis én gang i den ydre gennemløb.

Løkkernes rækkefølge er afgørende. Hvis vi placerer beløbet i den ydre løkke og mønten i den indre løkke, tæller vi permutationer (rækkefølgen betyder noget). For amount=5 med coins [1,2] tælles 1+2+2 og 2+1+2 separat. Hvis vi placerer mønten i den ydre løkke, tæller vi kombinationer (rækkefølgen betyder ikke noget): 1+2+2 og 2+1+2 er det samme. Coin Change II spørger efter kombinationer, så mønten er i den ydre løkke.

Et andet klassisk problem med den ubegrænsede rygsæk: Givet en stang med længden n og priser for hver stanglængde fra 1 til n skal du finde den maksimale indtjening ved at skære stangen optimalt. Hvert stykke med længden l kan sælges for price[l], og stykker kan genbruges (stangen kan skæres i flere stykker med samme længde). Det svarer direkte til den ubegrænsede rygsæk med W = n, hvor elementerne er de forskellige skærelængder.

Coin Change I (et andet problem) spørger efter det mindste antal mønter, der skal bruges til at danne et målbeløb. Her er dp[c] = det mindste antal mønter, der skal bruges til at danne beløbet c. Rekurrens: dp[c] = min(dp[c], dp[c - coin] + 1). Initialisér alle poster til inf undtagen dp[0] = 0. Dette er også en ubegrænset variant (mønter kan genbruges), så gennemløb fra venstre mod højre. Returnér dp[amount], hvis værdien er endelig, ellers -1.

De tre varianter af den ubegrænsede rygsæk bruger forskellige operationer på dp[c-coin]: Maksimér værdien: dp[c] = max(dp[c], dp[c-w] + v); initialisér til 0. Minimér omkostningen: dp[c] = min(dp[c], dp[c-coin] + 1); initialisér til inf, dp[0]=0. Tæl måder: dp[c] += dp[c-coin]; initialisér til 0, dp[0]=1. At genkende, hvilken variant der gælder, er halvdelen af arbejdet i interviewopgaver.

Alle varianter af den ubegrænsede rygsæk kører på O(n × W) tid og kræver O(W) plads, hvor n er antallet af elementtyper, og W er målbeløbet. I møntopgaver er n antallet af møntværdier. I interviews skal du angive varianten (maksimum/minimum/optælling), skrive 1D-DP'en og være tydelig om, hvorvidt den ydre løkke går over mønter eller beløb — interviewere ved, at denne forskel afprøver en dyb forståelse af DP.

Brug disse tegn til at identificere, hvilken variant der gælder: ubegrænset genbrug → ubegrænset (fremadrettet gennemløb); hvert element præcis én gang → 0/1 (baglæns gennemløb); problemet siger »et vilkårligt antal gange«, »ubegrænset forsyning« eller »genbrug tilladt« → ubegrænset. Eksempler: møntskifte, stangskæring og heltalsopdeling — alle er ubegrænsede. Delmængdesum, partitionering og 0/1-rygsæk — 0/1. Hvis du tager fejl her, får du forkerte svar, som er svære at fejlfinde.

Integer Break (LeetCode 343): Opdel et heltal n i mindst 2 positive heltal for at maksimere deres produkt. Dette er en ubegrænset rygsæk, hvor »elementerne« er heltallene fra 2 til n-1. Definér dp[i] = det maksimale produkt af heltal, hvis sum er i. For hvert element j fra 2 til i gælder dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Det viser, hvordan mønsteret for den ubegrænsede rygsæk kan generaliseres ud over møntproblemer.

I denne lektion lærte du: den ubegrænsede rygsæk gennemløber kapaciteten fra venstre mod højre for at tillade genbrug af elementer, Coin Change II tæller kombinationer ved at placere mønten i den ydre løkke, og de tre varianter — maksimér, minimér og tæl — adskiller sig kun ved DP-operationen og initialiseringen. Næste emne er at bruge 0/1-rygsækken til at løse Partition Equal Subset Sum.