Unbounded Knapsack och Coin Change II

I det obegränsade ryggsäcksproblemet kan varje objekt väljas ett godtyckligt antal gånger (till skillnad från 0/1-ryggsäcksproblemet, där varje objekt används högst en gång). Tillståndsdefinitionen är densamma — dp[c] = det maximala värdet som kan uppnås med kapaciteten c — men iterationsriktningen ändras. Eftersom objekten kan återanvändas vill vi tillåta att det aktuella objektet används igen när vi uppdaterar dp[c], så vi itererar över kapaciteten från vänster till höger (framåt).

Kom ihåg att vi i 0/1-ryggsäcksproblemet itererade från höger till vänster för att förhindra återanvändning. I det obegränsade ryggsäcksproblemet gör vi tvärtom: vi itererar från vänster till höger. När vi beräknar dp[c] har dp[c-w] redan uppdaterats i den aktuella genomgången — vilket betyder att objekt i redan kan ha inkluderats. Det är precis vad vi vill: objekt i kan läggas till igen i en lösning som redan innehåller objekt i.

Coin Change II frågar: givet myntvalörer och ett belopp, hur många olika sätt finns det att skapa beloppet (varje mynt kan användas obegränsat många gånger)? Detta är en variant av obegränsad ryggsäck där vi i stället för att maximera ett värde räknar kombinationer. Definiera dp[c] som antalet sätt att skapa beloppet c. Grundfall: dp[0] = 1 (ett sätt att skapa 0: att inte ta något).

För varje mynt itererar ni över beloppen från vänster till höger och summerar: dp[c] += dp[c - coin]. Grundfallet dp[0] = 1 initierar räkningen. Observera att den yttre loopen går över mynten och den inre loopen över beloppen — detta ger naturligt kombinationsantal (inte permutationer), eftersom varje myntvalör behandlas exakt en gång i en yttre genomgång.

Looparnas ordning är avgörande. Om vi placerar beloppet i den yttre loopen och myntet i den inre loopen räknar vi permutationer (ordningen spelar roll). För amount=5 med mynten [1,2] räknas 1+2+2 och 2+1+2 separat. Om vi placerar myntet i den yttre loopen räknar vi kombinationer (ordningen spelar ingen roll): 1+2+2 och 2+1+2 är samma. Coin Change II frågar efter kombinationer, så myntet ska ligga i den yttre loopen.

Ett annat klassiskt problem med obegränsad ryggsäck: givet en stav med längden n och priser för varje stavlängd från 1 till n, hitta den maximala intäkten genom att kapa staven optimalt. Varje del med längden l kan säljas för price[l], och delarna kan återanvändas (staven kan kapas i flera delar med samma längd). Detta motsvarar direkt obegränsad ryggsäck med W = n, där objekten är de olika kaplängderna.

Coin Change I (ett annat problem) frågar efter det minsta antalet mynt som krävs för att skapa ett målbelopp. Här är dp[c] = det minsta antalet mynt för att skapa beloppet c. Rekurrens: dp[c] = min(dp[c], dp[c - coin] + 1). Initiera alla poster till inf utom dp[0] = 0. Detta är också en obegränsad variant (mynt kan återanvändas), så iterera från vänster till höger. Returnera dp[amount] om värdet är ändligt, annars -1.

De tre varianterna av obegränsad ryggsäck använder olika operationer på dp[c-coin]: Maximera värdet: dp[c] = max(dp[c], dp[c-w] + v); initiera med 0. Minimera kostnaden: dp[c] = min(dp[c], dp[c-coin] + 1); initiera med inf, dp[0]=0. Räkna antalet sätt: dp[c] += dp[c-coin]; initiera med 0, dp[0]=1. Att känna igen vilken variant som gäller är halva utmaningen i intervjuproblem.

Alla varianter av obegränsad ryggsäck körs på O(n × W) tid och kräver O(W) utrymme, där n är antalet objekttyper och W är målbeloppet. För myntproblem är n antalet myntvalörer. Under intervjuer bör ni ange varianten (maximera/minimera/räkna), skriva 1D-DP och vara tydliga med om den yttre loopen går över mynt eller belopp — intervjuare vet att denna skillnad testar en djup förståelse av DP.

Använd följande signaler för att avgöra vilken variant som gäller: obegränsad återanvändning → obegränsad variant (framåtriktad iteration); varje objekt exakt en gång → 0/1 (bakåtriktad iteration); om problemet säger ”valfritt antal gånger”, ”obegränsad tillgång” eller ”återanvändning tillåten” → obegränsad variant. Exempel: Coin Change, Rod Cutting och Integer Break — alla är obegränsade. Subset Sum, Partition och 0/1 Knapsack — 0/1. Om ni väljer fel blir svaret fel, och sådana fel kan vara svåra att felsöka.

Integer Break (LeetCode 343): dela upp ett heltal n i minst två positiva heltal för att maximera deras produkt. Detta är en variant av obegränsad ryggsäck där ”objekten” är heltalen 2 till n-1. Definiera dp[i] = den maximala produkten av heltal vars summa är i. För varje objekt j från 2 till i gäller dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Detta visar hur mönstret för obegränsad ryggsäck kan generaliseras bortom myntproblem.

I den här lektionen har ni lärt er: obegränsad ryggsäck itererar över kapaciteten från vänster till höger för att tillåta återanvändning av objekt, Coin Change II räknar kombinationer genom att placera coin i den yttre loopen, och de tre varianterna — maximera, minimera och räkna — skiljer sig endast i DP-operationen och initieringen. Härnäst använder vi 0/1-ryggsäcksproblemet för att lösa Partition Equal Subset Sum.