Knapsack ottimizzato nello spazio
Ridurre una struttura 2D a una sola riga
Knapsack ottimizzato nello spazio è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Perché ottimizzare lo spazio
Una tabella completa richiede memoria pari a n per cap, che può diventare enorme con input grandi. L'ottimizzazione dello spazio riduce il costo a una singola riga riutilizzabile.
Conta solo l'ultima riga
Noti che ogni cella legge solo la riga precedente, mai dati più vecchi. Non è quindi necessario memorizzare l'intera griglia in una volta.
Ridurre a un array
Mantenga un unico array dp di lunghezza cap+1. Mentre elabora ogni oggetto, lo sovrascrive sul posto per rappresentare la nuova riga.
dp = [0] * (cap + 1)La trappola del riutilizzo
Se scorre la capacità da sinistra a destra, dp[w - wt[i]] potrebbe essere già stato aggiornato per lo stesso oggetto. Questo permetterebbe di prendere l'oggetto i due volte.
Iterare la capacità all'indietro
La soluzione consiste nel percorrere la capacità dal valore più alto a quello più basso. Procedere all'indietro garantisce che dp[w - wt[i]] contenga ancora il valore dell'oggetto precedente.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Perché funziona all'indietro
Quando calcola dp[w], l'indice più piccolo w - wt[i] è ancora intatto in questo giro, quindi riflette correttamente la riga precedente.
Fermarsi al peso
Le capacità inferiori a wt[i] non possono contenere l'oggetto, quindi il ciclo si ferma a wt[i]. Saltarle evita alcuni cicli inutili.
Il ciclo completo
L'intera soluzione consiste in due cicli annidati su un unico array. Gli oggetti all'esterno, la capacità all'indietro all'interno, e la risposta emerge da sola.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Leggere la cella finale
Dopo aver elaborato tutti gli oggetti, dp[cap] contiene il valore massimo. È lo stesso numero che fornirebbe la tabella 2D, ma usando molta meno memoria.
Stesso tempo, meno memoria
Non ha velocizzato l'algoritmo: il lavoro è ancora dell'ordine di n per cap. Ha soltanto ridotto la memoria da quadratica a lineare.
Quando conviene
Questo accorgimento è utile quando cap è grande e la griglia 2D supererebbe il limite di memoria. È una tecnica fondamentale nelle gare, che vale la pena memorizzare.
Verifica rapida
Verifichi la regola fondamentale dello zaino 1D.
Riepilogo
Ha ridotto la tabella 2D a un unico array e ha percorso la capacità all'indietro per mantenere la correttezza, sostituendo una memoria quadratica con una lineare. 🚀
Domande Frequenti
La lezione «Knapsack ottimizzato nello spazio» è gratuita?
Sì — il testo completo di «Knapsack ottimizzato nello spazio» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Knapsack ottimizzato nello spazio»?
Ridurre una struttura 2D a una sola riga Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Knapsack ottimizzato nello spazio»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Knapsack 0/1: prendere o lasciare
- Knapsack ottimizzato nello spazio
- DP illimitato e cambio di monete
- Somma di sottoinsiemi e partizionamento