Knapsack met geoptimaliseerd geheugengebruik

Een volledige tabel kost n maal cap aan geheugen, wat bij grote invoer enorm kan worden. Geheugenoptimalisatie verkleint dat tot één rij die je hergebruikt.

Elke cel leest alleen de vorige rij en nooit iets dat ouder is. Je hoeft dus niet het hele rooster tegelijk op te slaan.

Houd één dp-array met lengte cap+1 bij. Terwijl je elk voorwerp verwerkt, overschrijf je de array op zijn plaats zodat die de nieuwe rij voorstelt.

Als je de capaciteit van links naar rechts doorloopt, kan dp[w - wt[i]] al voor ditzelfde voorwerp zijn bijgewerkt. Dan zou je voorwerp i twee keer kunnen meenemen.

De oplossing is om de capaciteit van hoog naar laag te doorlopen. Achteruitgaan garandeert dat dp[w - wt[i]] nog de waarde van het vorige voorwerp bevat.

Wanneer je dp[w] berekent, is de kleinere index w - wt[i] deze ronde nog onaangeraakt. Daardoor stelt die de vorige rij voor, zoals bedoeld.

Capaciteiten onder wt[i] passen niet bij het voorwerp, dus de lus stopt bij wt[i]. Zo sla je een paar onnodige iteraties over.

De hele oplossing bestaat uit twee geneste lussen over één array. De voorwerpen buitenom, de capaciteit achteruit daarbinnen, en het antwoord volgt vanzelf.

Na alle voorwerpen bevat dp[cap] de maximale waarde. Het is hetzelfde getal dat de 2D-tabel zou opleveren, maar met veel minder geheugen.

Je hebt het algoritme niet versneld; het blijft werk van orde n maal cap. Je hebt alleen het geheugen teruggebracht van kwadratisch naar lineair.

Deze techniek helpt wanneer cap groot is en het 2D-rooster de geheugenlimiet zou overschrijden. Het is een vaste techniek in programmeerwedstrijden die het onthouden waard is.

Je hebt de 2D-tabel teruggebracht tot één array en de capaciteit achteruit doorlopen om correct te blijven, waarbij je kwadratisch geheugen hebt ingeruild voor lineair geheugen. 🚀