#Programmazione dinamicaIn questo capitolo sviluppiamo una tecnica molto potente per affrontare due categorie di problemi che ha senso trattare congiuntamente:
•problemi di ottimizzazione, cioè compiere scelte che portino al massimo guadagno (o, equivalentemente, alla minima spesa) possibile;•problemi di conteggio, cioè contare le soluzioni che rispettano una certa condizione.Consideriamo il seguente esempio pratico.
Rod Cutting
La Olinfo Srl compra barre di metallo molto lunghe per tagliarle e rivenderne pezzi più corti. Le barre possono essere lunghe un numero intero di metri da 1 a 𝑁 e dalla vendita di una barra di 𝑖 metri si ricavano 𝑝𝑖 euro. Effettuare i tagli non ha alcun costo. Aiuta la Olinfo Srl a ricavare il massimo possibile dalla vendita dei pezzi ottenuti da una barra di lunghezza 𝑁 metri!
Soluzione
Complichiamoci apparentemente la vita: rispondiamo non solo per una barra di lunghezza 𝑁, ma per tutte le possibili lunghezze 𝐿≤𝑁. Sia allora ricavo(𝐿) la risposta al problema per una barra di lunghezza 𝐿, per esempio ricavo(0)=0.
Se la Olinfo Srl ha una barra lunga 𝐿, e vende un pezzo di lunghezza 𝑖, questa ricava 𝑝𝑖+ricavo(𝐿−𝑖).
Prendiamoci un attimo per digerire questa formula: quello che stiamo affermando è che, se voglio tagliare un pezzo di lunghezza 𝑖 dalla barra lunga 𝐿, allora il massimo ricavo possibile da questa scelta è 𝑝𝑖, ovvero il guadagno della scelta stessa, sommato a ricavo(𝐿−𝑖), ovvero la soluzione ottimale per una barra lunga 𝐿−𝑖.
A questo punto siamo in grado di definire ricavo(𝐿): dato che tagliare un pezzo lungo 𝑖 genera un ricavo di 𝑝𝑖+ricavo(𝐿−𝑖), possiamo provare tutti gli 𝑖≤𝐿 e tenere quello che fa guadagnare di più. Formalmente:
ricavo(𝐿)=max{𝑝𝑖+ricavo(𝐿−𝑖)|𝑖=1,…,𝐿}.
Questa è un’implementazione di questa formula, lenta ma corretta:
ll ricavo(int L) {
ll ans = 0;
for (int i = 1; i <= L; i++)
ans = max(ans, p[i] + ricavo(L - i));
return ans;
}
La soluzione appena descritta è terribilmente inefficiente: calcoliamo i medesimi valori un numero di volte esponenziale in 𝑁. Se una volta ottenuti i valori si memorizzassero, ognuno verrebbe calcolato al più una volta. È quindi naturale salvare le risposte ai sottoproblemi una volta calcolate: questa tecnica è detta memoizzazione1.
Manteniamo opportuni array o mappe a indicare
1.se abbiamo già calcolato la risposta per un dato 𝐿;2.qual è questa risposta già calcolata2.In pratica modifichiamo leggermente l’implementazione della funzione ricavo.
ll ricavo(int L) {
if (memo[L] != -1)
return memo[L];
ll ans = 0;
for (int i = 1; i <= L; i++)
ans = max(ans, p[i] + ricavo(L - i));
return memo[L] = ans;
}
Un’osservazione tanto semplice ha effetti straordinari sulla complessità, che da esponenziale scende a 𝒪︀(𝑁2).
In questo e altri casi in cui esiste un naturale concetto di “taglia” di un sottoproblema possiamo calcolare le risposte ai vari sottoproblemi anche in maniera iterativa:
vector<ll> ricavo(N + 1); // inizializzato a zero
for (int L = 1; L <= N; L++)
for (int i = 1; i <= L; i++)
ricavo[L] = max(ricavo[L], p[i] + ricavo[L - i]);
Esercizio: capire perché una chiamata a ricavo(𝑁) comporta esattamente 2𝑁−1 chiamate a ricavo(0) e un totale di 2𝑁 chiamate a ricavo.
Facciamo un passo indietro e generalizziamo: spesso la soluzione di un problema si ricava più o meno facilmente da soluzioni per istanze “più piccole” dello stesso problema… che a loro volta si spezzano in istanze più piccole e così via, finché non rimangono istanze banali dette casi base. Dai casi base, in maniera iterativa o ricorsiva, si costruiscono le soluzioni ai sottoproblemi che intendiamo risolvere. Nota l’analogia con l’induzione matematica.
La programmazione dinamica è un concetto naturale, la sfida è identificare la famiglia di sottoproblemi da risolvere (di cui il problema originale farà parte) e capire come applicarla. Il modo migliore per imparare la programmazione dinamica è vedere qualche esempio e risolvere un buon numero di problemi.
Coin Combinations I CSES
Dato un sistema monetario di 𝑁 monete con valori distinti 𝑐1,…,𝑐𝑁 e una somma 𝑋, conta le pile distinte di monete con somma 𝑋, modulo 109+7. Due pile composte dalle stesse monete in ordine diverso si considerano distinte.
Prova il problema online: https://cses.fi/problemset/task/1635
Soluzione
Una ragionevole famiglia di sottoproblemi da risolvere in questo caso è, a sistema monetario fissato, l’insieme delle istanze con somma obiettivo 𝑌≤𝑋. Sia allora conta[𝑌] il numero di modi di ottenere somma 𝑌. Quante delle pile con somma 𝑌 hanno in cima una moneta di valore 𝑐𝑖? Esattamente conta[𝑌−𝑐𝑖]. Per contare le pile con somma 𝑌, quindi, possiamo sommare le pile con somma 𝑌 e ultima moneta 𝑐𝑖 al variare di 𝑐𝑖:
conta[𝑌]={0 se 𝑌<0
1 se 𝑌=0
∑𝑁𝑖=1conta[𝑌−𝑐𝑖] altrimenti
Una possibile implementazione è la seguente:
vector<int> conta(x + 1);
conta[0] = 1;
for (int y = 1; y <= x; y++)
for (int i = 0; i < n; i++)
if (y >= c[i])
conta[y] = (conta[y] + conta[y - c[i]]) % mod;
La complessità temporale è 𝒪︀(𝑁𝑋), quella spaziale 𝒪︀(𝑁+𝑋).
Coin Combinations II CSES
Come Coin Combinations I, ma conta questa volta i sottoinsiemi di monete: due pile ottenibili l’una dall’altra per permutazione si considerano ora equivalenti.
Prova il problema online: https://cses.fi/problemset/task/1636
Soluzione
Cerchiamo innanzitutto una pila rappresentante per ogni sottoinsieme di monete: una scelta ragionevole è quella le cui monete sono ordinate per valore crescente. La famiglia di sottoproblemi in questo caso è “In quanti modi fondamentalmente distinti si ottiene somma 𝑌 avendo a disposizione i primi 𝑖 tipi di monete?” al variare di 𝑌≤𝑋, 𝑖≤𝑁. Fissati i casi base, vale la ricorsione conta[𝑌][𝑖]= conta[𝑌][𝑖−1]+conta[𝑌−𝑐𝑖][𝑖]. L’implementazione diretta costa 𝒪︀(𝑁𝑋) tempo e memoria, ma si può fare meglio di così! Se immaginiamo di aggiungere al sistema monetario una moneta alla volta otteniamo una soluzione 𝒪︀(𝑁𝑋) tempo e 𝒪︀(𝑁+𝑋) memoria:
vector<int> conta(X + 1);
conta[0] = 1;
for (int i = 0; i < N; i++)
for (int y = c[i]; y <= X; y++)
conta[y] = (conta[y] + conta[y - c[i]]) % mod;
Alla fine di ogni iterazione del primo for, il vettore conta contiene a ogni posizione 𝑌 il numero di modi di ottenere 𝑌 con le prime 𝑖 monete. Nota che è importante l’ordine in cui si itera sugli 𝑌: se il for fosse stato da 𝑋 a 𝑐[𝑖], avremmo risolto il problema con l’ulteriore restrizione di poter usare ogni moneta al più una volta.
Massima sottosequenza comune CSES
Un array si dice sottosequenza di un altro array se il primo si può ottenere dal secondo eliminando alcuni elementi (possibilmente nessuno) senza cambiare l’ordine degli elementi rimanenti. Dati due array 𝑎1,𝑎2,…,𝑎𝑛 e 𝑏1,𝑏2,…,𝑏𝑚 rispettivamente di 𝑛 e 𝑚 elementi, si trovi una sottosequenza comune di lunghezza massima.
Prova il problema online: https://cses.fi/problemset/task/3403
Soluzione
Preoccupiamoci innanzitutto di trovare la lunghezza. Rispondiamo alla domanda per ogni possibile coppia prefisso del primo array e prefisso del secondo array: sia quindi lcs[𝑖][𝑗] la lunghezza della massima sottosequenza comune tra i primi 𝑖 elementi di 𝑎 e i primi 𝑗 elementi di 𝑏.
Calcoliamo lcs[𝑖][𝑗] supponendo di conoscere le risposte ai sottoproblemi più piccoli. Se 𝑎𝑖=𝑏𝑗, non c’è motivo di non includere gli ultimi elementi nella sequenza3. Se invece 𝑎𝑖≠𝑏𝑗, allora (almeno) uno tra 𝑎𝑖 non farà parte della sottosequenza comune, nel cui caso la risposta è una tra lcs[𝑖−1][𝑗] e lcs[𝑖][𝑗−1]. In altre parole, vale la seguente relazione:
lcs[𝑖][𝑗]={0 se 𝑖=0 o 𝑗=0
1+lcs[𝑖−1][𝑗−1] se 𝑎𝑖=𝑏𝑗
max(lcs[𝑖−1][𝑗],lcs[𝑖][𝑗−1]) altrimenti
Una possibile implementazione è la seguente:
vector<vector<int>> lcs(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i] == b[j])
lcs[i][j] = 1 + lcs[i - 1][j - 1];
else
lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
}
}
Data la matrice lcs, come ricostruiamo una sottosequenza massimale e non solo la sua lunghezza? In ordine inverso! Manteniamo due indici 𝑖,𝑗, inizialmente uguali a 𝑛,𝑚, che indicano i prefissi di cui stiamo calcolando la massima sottosequenza comune. Conoscendo gli array 𝑎𝑖,𝑏𝑗 e i valori di lcs possiamo capire la provenienza del valore (ottimo) di lcs[i][j] e, nel caso in cui 𝑎𝑖=𝑏𝑗, aggiungere un carattere alla risposta. Una possibile implementazione è la seguente.
int i = n, j = m;
vector<int> ans;
while (lcs[i][j]) {
if (a[i] == b[j]) {
ans.push_back(a[i]);
--i, --j;
} else {
if (lcs[i][j] == lcs[i - 1][j])
--i;
else
--j;
}
}
reverse(begin(ans), end(ans));
for (int i = 0; i < lcs[n][m]; i++)
cout << ans[i] << " ";
cout << '\n';
Monopoly Board Game OIS2022-23
Giochi a Monopoli su un tabellone circolare di 𝑁 caselle, numerate da 0 a 𝑁−1 con le caselle 𝑁− 1 e 0 adiacenti. Ogni casella ha un valore di imposta 𝑇𝑖 associato. Ogni volta che un giocatore atterra su una casella, deve pagare il rispettivo valore di imposta (il valore può essere negativo, nel cui caso il giocatore riceve denaro). Carlo parte dalla casella 0 e giocherà 𝐾 turni di Monopoli. Ogni turno lancia due dadi a 6 facce e avanza della somma dei due valori, poi paga l’imposta della casella su cui atterra. Se i due valori dei dadi sono uguali, dopo aver mosso e pagato, lancia nuovamente i dadi. Carlo può muovere al massimo tre volte in un singolo turno, dopodiché il suo turno termina automaticamente (anche se i due valori dei dadi sono uguali). Poiché non accetti di perdere, hai truccato i dadi e controlli l’esito di tutti i lanci. Il tuo obiettivo è massimizzare la quantità di denaro che Carlo perde durante il gioco.
Prova il problema online: https://training.olinfo.it/task/ois_monopoly
Soluzione
Una valida famiglia di sottoproblemi da risolvere in questo caso è “qual è la risposta per 𝑘 turni se termino il 𝑘-esimo turno sulla casella 𝑖 con 𝑙 lanci”. Alternativamente, il limite di tempo permette una soluzione più lenta ma più semplice i cui stati sono solo le coppie 𝑘, 𝑖 con 0≤𝑘≤𝐾 e 0≤𝑖< 𝑁. Un’implementazione del primo approccio si trova su https://github.com/franfill1/training.olinfo.it-solutions/blob/master/src/ois_monopoly.cpp, una del secondo su https://github.com/lorenzo-ferrari/olinfo/blob/main/src/ois_monopoly.cpp.
Invitiamo a notare che per quanto la programmazione dinamica in questione abbia 𝒪︀(𝑁𝐾) stati, i valori all’(𝑖+1)-esimo turno dipendono esclusivamente da quelli all’𝑖-esimo turno, quindi la soluzione si può implementare in 𝒪︀(𝑁) memoria.
#Esercizi consigliatiConsigliamo innanzitutto di dare un’occhiata ai problemi della sezione “Dynamic Programming” su CSES: https://cses.fi/problemset/.
Anche Atcoder offre una raccolta di problemi di programmazione dinamica molto valida: https://atcoder.jp/contests/dp.
Pranzo dalla nonna (https://training.olinfo.it/task/ois_nonna)
Treni (https://training.olinfo.it/task/preoii_treni)
ZigZag (https://training.olinfo.it/task/zigzag)
Sushi variegato (https://training.olinfo.it/task/preoii_yutaka)
Corsa Contro il Tempo 2 (https://training.olinfo.it/task/tai_cct2)
Episodio III: la coda per il buffet (https://training.olinfo.it/task/oii_coda)
Tulip Bouquets (https://training.olinfo.it/task/ois_tulips)
1No, non è un errore di battitura. Si chiama memoizzazione, non memorizzazione.2Le due informazioni si possono accorpare se a un valore inutilizzato (come −1 in questo caso) si assegna il significato di “risposta non ancora calcolata”.3È intuitivo, ma perché? Va dimostrato che per ogni soluzione ottimale, esiste una soluzione almeno altrettanto buona.