Knapsack 0/1 e ottimizzazione dello spazio

Il problema dello zaino 0/1: dati n elementi, ciascuno con un peso w[i] e un valore v[i], e uno zaino con capacità W, scelga gli elementi in modo da massimizzare il valore totale senza superare la capacità. Ogni elemento viene preso esattamente una volta (0 = escludere, 1 = includere). Questo è il modello fondamentale di un'ampia famiglia di problemi di DP da colloquio, tra cui partition-equal-subset-sum e target-sum.

Definisca dp[i][c] come il valore massimo ottenibile usando i primi i elementi con capacità c. Per l'elemento i ci sono due possibilità: saltarlo (dp[i-1][c]) oppure includerlo se w[i] <= c (dp[i-1][c-w[i]] + v[i]). La ricorrenza è: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) quando w[i] <= c; altrimenti dp[i][c] = dp[i-1][c]. Caso base: dp[0][c] = 0 per ogni c.

La tabella 2D contiene (n+1) x (W+1) celle e viene compilata riga per riga per ciascun elemento. Dopo aver compilato tutte le righe, dp[n][W] contiene il valore massimo. L'esecuzione richiede O(n × W) di tempo e O(n × W) di spazio: si tratta di una complessità pseudopolinomiale, efficiente quando W è piccolo.

L'osservazione fondamentale è che la riga i dipende solo dalla riga i-1. È quindi possibile usare un unico array 1D e aggiornarlo in loco. Tuttavia, se si itera sulla capacità c da sinistra a destra (da piccola a grande), l'elemento i potrebbe essere contato due volte: si potrebbe usare il valore aggiornato per c-w[i], che include già l'elemento i. Iterare da destra a sinistra (da grande a piccola) garantisce che ogni elemento venga usato al massimo una volta durante l'aggiornamento di una riga.

Mantenendo un solo array e iterando sulla capacità da W fino a w[i], si ottiene lo stesso risultato della tabella 2D con O(W) di spazio. La complessità temporale rimane O(n × W). Questa ottimizzazione dello spazio è fondamentale da ricordare: nei colloqui viene chiesto spesso di ridurre lo zaino 2D a una soluzione 1D.

Per trovare quali elementi sono stati selezionati, è necessaria la tabella 2D completa. Dopo averla compilata, parta da dp[n][W] e proceda a ritroso: se dp[i][c] != dp[i-1][c], l'elemento i è stato incluso; ne sottragga il peso da c e passi alla riga i-1. Continui fino a i = 0. L'ottimizzazione 1D elimina la possibilità di ricostruire la soluzione.

Consideri gli elementi: weights=[2,3,4,5], values=[3,4,5,6], W=8. La soluzione ottimale consiste nello scegliere gli elementi di peso 3 (valore 4) e di peso 5 (valore 6): peso totale 8 e valore 10. In alternativa, si possono scegliere gli elementi di peso 2 e 5, ottenendo un valore totale di 9, oppure quelli di peso 2 e 3, ottenendo un valore di 7. La DP trova correttamente il massimo, cioè 10. Si noti che l'approccio greedy (scegliere il rapporto valore/peso più alto) sceglierebbe per primo l'elemento con rapporto 1.5 (peso 2, valore 3), ma non è sempre ottimale.

Nello zaino frazionario è possibile prendere frazioni degli elementi. Questo problema si risolve con un approccio greedy, ordinando gli elementi in base al rapporto valore/peso. Nello zaino 0/1, gli elementi sono indivisibili: l'approccio greedy fallisce ed è necessaria la DP. Gli intervistatori usano questa distinzione per verificare che si sappia quando è applicabile un approccio greedy. Se le viene chiesta la variante frazionaria, menzioni subito l'approccio greedy con ordinamento; per la variante 0/1, scelga la DP.

Lo zaino 0/1 è NP-completo, eppure lo si risolve in O(nW) di tempo. La contraddizione si risolve considerando che O(nW) è pseudopolinomiale: W è un valore, non la dimensione dell'input. La rappresentazione binaria di W richiede O(log W) bit, quindi la complessità effettiva è O(n × 2^(log W)), esponenziale rispetto alla dimensione dell'input. Quando W è piccolo (ad esempio 10⁴), la DP è pratica; quando W può arrivare a 10⁹, sono necessari approcci diversi.

Se l'intervistatore impone che W sia molto grande (ad esempio 10⁹), ma n sia piccolo, la DP standard non è adatta. Le alternative includono: (1) meet-in-the-middle in O(2^(n/2) × n) di tempo, (2) un'approssimazione greedy per la variante frazionaria oppure (3) branch-and-bound. Per la maggior parte dei problemi da colloquio con W <= 10⁵, la DP 1D con iterazione all'indietro è la risposta attesa.

Quando W è molto grande ma n è piccolo (ad esempio n=40), la DP standard O(nW) non è praticabile, mentre la forza bruta 2^n è troppo lenta. Il meet-in-the-middle divide gli elementi in due metà, enumera tutti i 2^(n/2) sottoinsiemi di ciascuna metà e li abbina in modo ottimale. Si ordina una metà in base al peso, quindi, per ogni sottoinsieme dell'altra metà, si usa la ricerca binaria per trovare l'abbinamento migliore entro il limite di capacità. L'esecuzione richiede O(2^(n/2) × n), rendendo l'approccio pratico fino a n=40.

Metta alla prova la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato: la DP dello zaino 0/1 ha lo stato dp[i][c], che rappresenta il valore massimo con i elementi e capacità c, la ricorrenza sceglie se saltare o includere ciascun elemento e l'ottimizzazione dello spazio 1D itera sulla capacità da destra a sinistra per evitare di contare due volte gli elementi. Ora esploreremo lo zaino illimitato, in cui gli elementi possono essere riutilizzati, e lo applicheremo a Coin Change II.