Knapsack illimitato e Coin Change II

Nello zaino illimitato, ogni elemento può essere preso un numero qualsiasi di volte (a differenza dello zaino 0/1, in cui ogni elemento viene usato al massimo una volta). La definizione dello stato è la stessa: dp[c] = valore massimo ottenibile con capacità c; cambia però la direzione di iterazione. Poiché gli elementi sono riutilizzabili, quando aggiorniamo dp[c] vogliamo consentire un nuovo utilizzo dell'elemento corrente, quindi iteriamo sulla capacità da sinistra a destra (in avanti).

Si ricordi che nello zaino 0/1 si iterava da destra a sinistra per impedire il riutilizzo. Nello zaino illimitato si fa il contrario: si itera da sinistra a destra. Nel calcolo di dp[c], dp[c-w] è già stato aggiornato durante il passaggio corrente: ciò significa che l'elemento i potrebbe essere già stato incluso. È esattamente ciò che si desidera: l'elemento i può essere aggiunto di nuovo a una soluzione che contiene già l'elemento i.

Coin Change II chiede: date le denominazioni delle monete e un importo, contare il numero di modi distinti per ottenere quell'importo (ogni moneta può essere usata un numero illimitato di volte). Si tratta di una variante dello zaino illimitato in cui, invece di massimizzare il valore, si contano le combinazioni. Definisca dp[c] come il numero di modi per ottenere l'importo c. Caso base: dp[0] = 1 (un modo per ottenere 0: non prendere nulla).

Per ogni moneta, iteri sugli importi da sinistra a destra e accumuli: dp[c] += dp[c - coin]. Il caso base dp[0] = 1 inizializza il conteggio. Si noti che il ciclo esterno scorre le monete e quello interno gli importi: in questo modo si ottengono naturalmente i conteggi delle combinazioni (non delle permutazioni), perché ogni denominazione viene considerata esattamente una volta durante il passaggio esterno.

L'ordine dei cicli è fondamentale. Se si mette amount nel ciclo esterno e coin in quello interno, si contano le permutazioni (l'ordine è importante). Per amount=5 con coins [1,2], 1+2+2 e 2+1+2 vengono contate separatamente. Se si mette coin nel ciclo esterno, si contano le combinazioni (l'ordine non è importante): 1+2+2 e 2+1+2 sono la stessa combinazione. Coin Change II richiede le combinazioni, quindi coin va messo nel ciclo esterno.

Un altro classico problema dello zaino illimitato: data una sbarra di lunghezza n e i prezzi per ogni lunghezza da 1 a n, trovi il ricavo massimo tagliando la sbarra in modo ottimale. Ogni pezzo di lunghezza l può essere venduto a price[l] e i pezzi possono essere riutilizzati (la sbarra può essere divisa in più pezzi della stessa lunghezza). Questo problema corrisponde direttamente allo zaino illimitato con W = n, in cui gli elementi sono le diverse lunghezze dei tagli.

Coin Change I (un problema diverso) chiede il numero minimo di monete necessario per ottenere un importo obiettivo. Qui dp[c] = numero minimo di monete per ottenere l'importo c. Ricorrenza: dp[c] = min(dp[c], dp[c - coin] + 1). Inizializzi tutte le celle a inf, tranne dp[0] = 0. Anche questo è un problema illimitato (le monete possono essere riutilizzate), quindi iteri da sinistra a destra. Restituisca dp[amount] se è finito; altrimenti restituisca -1.

Le tre varianti dello zaino illimitato usano operazioni diverse su dp[c-coin]: Massimizzare il valore: dp[c] = max(dp[c], dp[c-w] + v); inizializzare a 0. Minimizzare il costo: dp[c] = min(dp[c], dp[c-coin] + 1); inizializzare a inf, dp[0]=0. Contare i modi: dp[c] += dp[c-coin]; inizializzare a 0, dp[0]=1. Riconoscere quale variante si applica è metà del lavoro nei problemi da colloquio.

Tutte le varianti dello zaino illimitato richiedono O(n × W) di tempo e O(W) di spazio, dove n è il numero di tipi di elementi e W è l'importo obiettivo. Nei problemi sulle monete, n è il numero di denominazioni. Nei colloqui, indichi la variante (massimo/minimo/conteggio), scriva la DP 1D e specifichi chiaramente se il ciclo esterno scorre le monete o l'importo: gli esaminatori sanno che questa distinzione verifica una comprensione approfondita della DP.

Usi questi segnali per identificare la variante corretta: riutilizzo illimitato → zaino illimitato (iterazione in avanti); ogni elemento esattamente una volta → zaino 0/1 (iterazione all'indietro); se il problema dice 'any number of times', 'infinite supply' o 'reuse allowed' → zaino illimitato. Esempi: cambio delle monete, taglio della sbarra e Integer Break sono tutti problemi illimitati. Subset sum, partition e 0/1 knapsack sono problemi 0/1. Sbagliare questa distinzione porta a risposte errate difficili da correggere.

Integer Break (LeetCode 343): dividere un intero n in almeno 2 interi positivi per massimizzarne il prodotto. Si tratta di uno zaino illimitato in cui gli 'elementi' sono gli interi da 2 a n-1. Definisca dp[i] = prodotto massimo di interi la cui somma è i. Per ogni elemento j da 2 a i, dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Questo mostra come il modello dello zaino illimitato si generalizzi oltre il contesto delle monete.

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

In questa lezione ha imparato: lo zaino illimitato itera sulla capacità da sinistra a destra per consentire il riutilizzo degli elementi, Coin Change II conta le combinazioni mettendo coin nel ciclo esterno e le tre varianti — massimizzare, minimizzare e contare — differiscono solo per l'operazione DP e l'inizializzazione. Ora useremo lo zaino 0/1 per risolvere Partition Equal Subset Sum.