Plassoptimalisert ryggsekk

En full tabell bruker n ganger cap minne, noe som kan bli enormt for store inndata. Plassoptimalisering reduserer dette til én rad som du gjenbruker.

Legg merke til at hver celle bare leser den forrige raden, aldri noe eldre. Derfor trenger du ikke å lagre hele rutenettet samtidig.

Behold ett dp-array med lengde cap+1. Når du behandler hver gjenstand, overskriver du arrayet på stedet slik at det representerer den nye raden.

Hvis du går gjennom kapasiteten fra venstre mot høyre, kan dp[w - wt[i]] allerede være oppdatert for denne samme gjenstanden. Da ville du kunne ta gjenstand i to ganger.

Løsningen er å gå gjennom kapasiteten fra høy til lav. Når du går baklengs, er du garantert at dp[w - wt[i]] fortsatt inneholder verdien fra forrige rad.

Når du beregner dp[w], er den mindre indeksen w - wt[i] fortsatt urørt i denne runden, så den gjenspeiler raden over slik den skal.

Kapasiteter under wt[i] kan ikke romme gjenstanden, så løkken stopper ved wt[i]. Ved å hoppe over dem sparer du noen ufarlige gjennomløp.

Hele løsningen består av to nøstede løkker over ett array. Gjenstandene ytterst, kapasiteten baklengs innerst, og svaret kommer av seg selv.

Etter alle gjenstandene inneholder dp[cap] maksimumsverdien. Det er det samme tallet som 2D-tabellen ville gitt, men med langt mindre minnebruk.

Du gjorde ikke algoritmen raskere; den bruker fortsatt arbeid på størrelsesorden n ganger cap. Du reduserte bare minnebruken fra kvadratisk til lineær.

Dette trikset redder deg når cap er stor og 2D-rutenettet ville overskredet minnegrensen. Det er en klassiker i konkurranser som er verdt å huske.

Du reduserte 2D-tabellen til ett array og gikk gjennom kapasiteten baklengs for å holde løsningen korrekt. Dermed byttet du kvadratisk minnebruk mot lineær. 🚀