Dynamic Programming
Dynamic Programming is mainly an optimization over plainย recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.
For example, if we write simple recursive solution forย Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.
Quindi in breve, memorizziamo il risultato ottenuto risolvendo un particolare problema in una tabella DP (vettore, matrice, dizionario). La tabella deve contenere un elemento per ogni sottoproblema che dobbiamo risolvere, i casi base li memorizziamo direttamente nelle posizioni relative.
Iterazione bottom-up
- Si parte dai problemi risolubili come basi base
- Si sale verso problemi via via piรน grandi ...
- ... fino a raggiungere il problema originale
Hateville
Problema
- Hateville รจ un villaggio particolare, composto da
case, numerate da a lungo una singola strada. - Ad Hateville ognuno odia i propri vicini della porta accanto, da entrambi i lati.
- Quindi, il vicino i odia i vicini
e (se esistenti). Hateville vuole organizzare una sagra e vi ha affidato il compito di raccogliere i fondi. - Ogni abitante
ha intenzione di donare una quantitร , ma non intende partecipare ad una raccolta fondi a cui partecipano uno o entrambi i propri vicini.
- Scrivere un algoritmo che dato il vettore
, restituisca la quantitร massima di fondi che puรฒ essere raccolta - Bonus: restituire un sottoinsieme di indici
tale che il totale dei fondi raccolti sia massimale
Esempio
Vettore donazioni:
Raccolta fondi massima:
Insieme indici:
Soluzione
ร possibile definire una formula ricorsiva che permetta di calcolare il sottoinsieme di case che, se selezionate, dร origine alla maggior quantitร di donazioni.
Sia
Cosa succede se non accetto la donazione di una casa?
Cosa succede se accetto la sua donazione?
Come faccio a decidere se accettare o meno?
Soluzione ricorsiva
Equazione di ricorrenza
Ovviamente non vale la pena scrivere un algoritmo ricorsivo, basato su divide-et-impera, per risolvere il problema, visto che la complessitร sarebbe
Implementazione
int hateVille(const vector<int>& D) {
return hateVilleHelper(D, D.size() - 1);
}
int hateVilleHelper(const vector<int>& D, int i) {
if(i < 0)
return 0;
else if (i == 0)
return D[0];
else
return max(hateVilleHelper(D, i - 1), hateVilleHelper(D, i - 2) + D[i]);
}
- Time complexity:
(n รจ il numero di elementi nell'array) - Space complexity:
Graficamente, sta avvenendo questo:
graph TD
A(10) -->|โ| B(5)
A -->|โ
| C(5)
B -->|โ| D(5)
B -->|โ
| E(10)
C -->|โ| F(10)
C -->|โ
| G(0)
D -->|โ| H(10)
D -->|โ
| I(0)
E -->|โ| J(0)
E -->|โ
| K(0)
F -->|โ| L(0)
F -->|โ
| M(0)
H -->|โ| N(0)
H -->|โ
| O(0)Soluzione iterativa con dynamic programming
Invece di ricalcolare piรน volte gli stessi sottoproblemi, utilizziamo un vettore DP in cui salviamo il risultato di un sottoproblema.
Sia quindi
Equazione di ricorrenza
Implementazione
int hateVille(const vector<int>& D) {
int n = D.size();
vector<int> DP(n + 1);
DP[0] = 0;
DP[1] = D[0];
for(int i = 2; i < n + 1; i++)
DP[i] = max(DP[i-1], DP[i-2] + D[i-1]);
// + D[i-1] perchรจ DP รจ shiftato a destra di 1, visto che DP[0] = 0
return DP[n];
}
- Time complexity:
(n รจ il numero di elementi nell'array) - Space complexity:
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/HateVille.png)
Ottenere gli indici delle case selezionate
Abbiamo quindi ottenuto il valore della soluzione massimale, ma non conosciamo gli indici delle case selezionate! Possiamo tuttavia ricostruirci la soluzione originale. Come?
- Si guarda lโelemento
. Da cosa deriva il suo valore? - Se
, la casa non รจ stata selezionata, dunque si prende la soluzione fino a senza aggiungere nulla - Se
, la casa รจ stata selezionata, dunque si prende la soluzione fino a e si aggiunge
- Se
Implementazione
vector<int> hateVille(const vector<int>& D) {
int n = D.size();
vector<int> DP(n + 1);
DP[0] = 0;
DP[1] = D[0];
for(int i = 2; i < n + 1; i++)
DP[i] = max(DP[i-1], DP[i-2] + D[i-1]);
return solution(DP, n);
}
vector<int> solution(const vector<int>& DP, int i) {
if(i <= 0)
return {};
else if(i == 1)
return {0};
else if(DP[i] == DP[i-1])
return solution(DP, i - 1);
else {
vector<int> sol = solution(DP, i-2);
sol.push_back(i-1);
return sol;
}
}
- Time complexity:
(n รจ il numero di elementi nell'array) - Space complexity:
Si potrebbe migliorare la complessitร spaziale di hateville() solo nel caso in cui non ci servissero gli indici delle case. Se invece vogliamo ricostruire la soluzione รจ necessario avere un array di supporto.
Zaino (knapsack)
Problema
Dato un insieme di oggetti, ognuno caratterizzato da un peso e un profitto, e uno "zaino" con un limite di capacitร , individuare un sottoinsieme di oggetti
- il cui peso sia inferiore alla capacitร dello zaino;
- il valore totale degli oggetti sia massimale, i.e. piรน alto o uguale al valore di qualunque altro sottoinsieme di oggetti
Esempio
- Pesi:
- Profitti:
- Capacitร :
- Soluzione:
, ossia
Soluzione
Dato uno zaino di capacitร
Cosa succede se non prendiamo l'oggetto?
La capacitร non cambia, non cโรจ profitto.
Cosa succede se prendiamo l'oggetto?
Sottraiamo il peso dalla capacitร e aggiungiamo il profitto relativo.
Come faccio a scegliere la soluzione migliore?
Soluzione iterativa con dynamic programming
Invece di ricalcolare piรน volte gli stessi sottoproblemi, utilizziamo una matrice
Equazione di ricorrenza
Implementazione
int knapsack(const vector<int>& weight, const vector<int>& profit, int C) {
int n = weight.size();
vector<vector<int>> DP(n + 1, vector<int>(C + 1));
for(int i = 0; i < C + 1; i++)
DP[0][i] = 0;
for(int i = 0; i < n + 1; i++)
DP[i][0] = 0;
for(int i = 1; i < n + 1; i++) {
for(int c = 1; c < C + 1; c++) {
if(weight[i - 1] > c) {
//If it's too heavy, don't pick it!
DP[i][c] = DP[i - 1][c];
}
else {
//Should we pick it? Max of both!
DP[i][c] = max(DP[i - 1][c], DP[i - 1][c - weight[i - 1]] + profit[i - 1]);
}
}
}
return DP[n][C];
}
- Time complexity:
(n รจ il numero di elementi dati in input, C la capacitร ) - Space complexity:
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/Knapsack.png)
In realtร c'รจ da fare una piccola precisazione sulla complessitร spaziale di questo algoritmo. Infatti, sebbene sembri un algoritmo polinomiale, in realtร รจ definito come "pseudo-polinomiale". Questo perchรจ sono necessari
Esempio:
Scegliamo come input i numeri che hanno
Input di
Input di
Input di
Input di
e cosรฌ via...
Quindi la complessitร spaziale รจ
Soluzione ricorsiva
Equazione di ricorrenza
Ovviamente non vale la pena scrivere un algoritmo ricorsivo, basato su divide-et-impera, per risolvere il problema, visto che la complessitร sarebbe
Implementazione
int knapsack(const vector<int>& weight, const vector<int>& profit, int c) {
int n = weight.size();
return knapsackHelper(weight, profit, n, c);
}
int knapsackHelper(const vector<int>& weight, const vector<int>& profit, int i, int c) {
if(i == 0 || c == 0)
return 0;
else if(weight[i - 1] > c)
return knapsackHelper(weight, profit, i - 1, c);
else
return max (
knapsackHelper(weight, profit, i - 1, c),
knapsackHelper(weight, profit, i - 1, c - weight[i - 1]) + profit[i - 1]
);
}
- Time complexity:
(n รจ il numero di elementi nell'array) - Space complexity:
Potremmo perรฒ utilizzare lo stesso approccio del dynamic programming e salvarci il risultato del sottoproblema una volta risolto. In questo caso, anche se ricorsivamente, daremo un'occhiata alla tabella
Soluzione ricorsiva con memoization
Memoization (annotazione)
Tecnica che fonde lโapproccio di memorizzazione della programmazione dinamica con lโapproccio top-down di divide-et-impera.
Si crea una tabella DP, inizializzata con un valore speciale che indica che un sottoproblema non รจ ancora stato risolto.
Quando si deve risolvere un sottoproblema, si controlla nella tabella se รจ giร stato risolto:
- SI: si usa il risultato della tabella
- NO: si calcola il risultato e lo si memorizza
In tal modo, ogni sottoproblema viene calcolato una sola volta e memorizzato come nella versione bottom-up.
Implementazione
int knapsack(const vector<int>& weight, const vector<int>& profit, int c) {
int n = weight.size();
vector<vector<int>> DP(n + 1, vector<int>(c + 1, -1));
return knapsackHelper(weight, profit, n, c, DP);
}
int knapsackHelper(const vector<int>& weight, const vector<int>& profit, int i, int c, vector<vector<int>>& DP) {
if(i == 0 || c == 0)
return 0;
else if(DP[i][c] != -1)
return DP[i][c];
else if(weight[i - 1] > c)
return DP[i][c] = knapsackHelper(weight, profit, i - 1, c, DP);
else {
return DP[i][c] = max (
knapsackHelper(weight, profit, i - 1, c, DP),
knapsackHelper(weight, profit, i - 1, c - weight[i - 1], DP) + profit[i - 1]
);
}
}
- Time complexity:
(n รจ il numero di elementi nell'array) - Space complexity:
(n per la ricorsione, nC per la tabella )
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/Memoization.png)
Applicata in questo modo, non cโรจ alcun vantaggio nellโutilizzare la tecnica di memoization rispetto al metodo iterativo, tuttavia permette di tradurre in fretta le espressioni ricorsive.
Invece di utilizzare una tabella, si potrebbe utilizzare un dizionario, evitando cosรฌ di fare inizializzazioni. Il costo di esecuzione sarebbe pari a
Soluzione iterativa con dynamic programming con spazio ottimizzato
Implementazione
int knapsack(const vector<int>& weight, const vector<int>& profit, int C) {
int n = weight.size();
vector<int> DP(C + 1, 0);
for(int i = 0; i < n; i++)
for(int c = C; c >= 0; c--)
if(weight[i] <= c)
DP[c] = max(DP[c], DP[c - weight[i]] + profit[i]);
return DP[C];
}
- Time complexity:
(n รจ il numero di elementi nell'array, C la capacitร ) - Space complexity:
Zaino (knapsack) senza limiti
Problema
Il problema รจ il medesimo di #Zaino (knapsack), ma non abbiamo limiti sul numero di volte che un oggetto puรฒ essere selezionato.
Soluzione
Dato uno zaino di capacitร
Soluzione ricorsiva con memoization
ร sufficiente non fare
Equazione di ricorrenza
Implementazione
int knapsack(const vector<int>& weight, const vector<int>& profit, int c) {
int n = weight.size();
vector<vector<int>> DP(n + 1, vector<int>(c + 1, -1));
return knapsackHelper(weight, profit, n, c, DP);
}
int knapsackHelper(const vector<int>& weight, const vector<int>& profit, int i, int c, vector<vector<int>>& DP) {
if(i == 0 || c == 0)
return 0;
else if(DP[i][c] != -1)
return DP[i][c];
else if(weight[i - 1] > c)
return DP[i][c] = knapsackHelper(weight, profit, i - 1, c, DP);
else {
return DP[i][c] = max (
knapsackHelper(weight, profit, i - 1, c, DP),
knapsackHelper(weight, profit, i, c - weight[i - 1], DP) + profit[i - 1]
);
}
}
Soluzione ricorsiva con dynamic programming e spazio ottimizzato
In realtร , non avendo limiti al numero di volte che un oggetto puรฒ essere preso, possiamo ottimizzare lo spazio usato ed evitare di usare una matrice
Perchรจ possiamo fare questo?
Perchรจ in #Zaino (knapsack) dovevo tenere conto se un oggetto era stato preso oppure no, quindi avevo bisogno di una seconda dimensione per tenere traccia di quali oggetti avevo considerato. Qui posso riprenderli quanto voglio, quindi posso semplificare la formula. Ovviamente questo approccio rende piรน difficile ricostruire la soluzione, ma vedremo in seguito come risolvere questo problema.
Praticamente ora scorriamo la "matrice" per colonne invece che per righe; proviamo quindi tutti gli oggetti per
Implementazione
int unboundedKnapsack(const vector<int>& weight, const vector<int>& profit, int C) {
int n = weight.size();
vector<int> DP(C+1, 0);
for (int c = 0; c < C + 1; c++)
for (int i = 0; i < n; i++)
if (weight[i] <= c)
DP[c] = max(DP[c], DP[c-weight[i]] + profit[i]);
return DP[C];
}
- Time complexity:
(n รจ il numero di elementi nell'array) - Space complexity:
(n per la ricorsione, nC per la tabella )
Ottenere gli indici degli oggetti selezionati
Come detto prima, questo approccio rende piรน difficile ricostruire la soluzione, ma possiamo tenerci traccia in un altro vettore quali oggetti abbiamo preso. Poi, ricorsivamente, sottraiamo alla capacitร totale il peso dell'oggetto selezionato e infine li aggiungiamo all'array.
Implementazione
vector<int> unboundedKnapsack(const vector<int>& weight, const vector<int>& profit, int C) {
int n = weight.size();
vector<int> DP(C+1, 0);
vector<int> pos(C+1, -1);
for (int c = 0; c < C + 1; c++) {
for (int i = 0; i < n; i++) {
if (weight[i] <= c) {
int val = DP[c-weight[i]] + profit[i];
if(val > DP[c]) {
DP[c] = val;
pos[c] = i;
}
}
}
}
return solution(weight, pos, C);
}
vector<int> solution(const vector<int>& weight, const vector<int>& pos, int C) {
if(C == 0 || pos[C] < 0)
return { };
else {
vector<int> sol = solution(weight, pos, C - weight[pos[C]]);
sol.insert(sol.begin(), pos[C]);
return sol;
}
}