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

Hateville

Problema

  1. Scrivere un algoritmo che dato il vettore D, restituisca la quantitร  massima di fondi che puรฒ essere raccolta
  2. Bonus: restituire un sottoinsieme di indici SโІ1,...,n tale che il totale dei fondi raccolti T=โˆ‘iโˆˆSD[i] sia massimale

Esempio

Vettore donazioni: D=[10,5,5,10]
Raccolta fondi massima: 20
Insieme indici: {1,4}

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 HV(i) uno dei possibili insiemi di indici da selezionare per ottenere una donazione ottimale dalle prime i case di Hateville, numerate 1...n.

Cosa succede se non accetto la donazione di una casa?

HV(i)=HV(iโˆ’1)

Cosa succede se accetto la sua donazione?

HV(i)={i}โˆชHV(iโˆ’2)

Come faccio a decidere se accettare o meno?

HV(i)=max(HV(iโˆ’1)โžNonย Preso,{i}โˆชHV(iโˆ’2))โžPreso

Soluzione ricorsiva

Equazione di ricorrenza

HV(i)={โˆ…i=0D[1]i=1max(HV(iโˆ’1),{i}โˆชHV(iโˆ’2))iโ‰ฅ2

Ovviamente non vale la pena scrivere un algoritmo ricorsivo, basato su divide-et-impera, per risolvere il problema, visto che la complessitร  sarebbe O(2n). Tuttavia, per fini didattici, ecco il codice per farlo.

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]);
}

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 DP[i] il valore della massima quantitร  di donazioni che possiamo ottenere dalle prime i case di Hateville. DP[n] รจ il valore della soluzione ottima.

Equazione di ricorrenza

HV(i)={0i=0D[1]i=1max(DP[iโˆ’1],DP[iโˆ’2]+DP[i])iโ‰ฅ2

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];
}

HateVille.png800

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?

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;
    }
}

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

Esempio

Soluzione

Dato uno zaino di capacitร  C e n oggetti caratterizzati da peso w e profitto p, definiamo DP[i][c] come il massimo profitto che puรฒ essere ottenuto dai primi iโ‰คn oggetti contenuti in uno zaino di capacitร  cโ‰คC. Dunque il massimo profitto ottenibile dal problema originale รจ rappresentato da DP[n][C].

Cosa succede se non prendiamo l'oggetto?

DP[i][c]=DP[iโˆ’1][c]

La capacitร  non cambia, non cโ€™รจ profitto.

Cosa succede se prendiamo l'oggetto?

DP[i][c]=DP[iโˆ’1][cโˆ’w[i]]+p[i]

Sottraiamo il peso dalla capacitร  e aggiungiamo il profitto relativo.

Come faccio a scegliere la soluzione migliore?

DP[i][c]=max(DP[iโˆ’1][cโˆ’w[i]]+p[i]โžPreso,DP[iโˆ’1][c])โžNonย Preso

Soluzione iterativa con dynamic programming

Invece di ricalcolare piรน volte gli stessi sottoproblemi, utilizziamo una matrice DP che riempiamo iterativamente, iniziando a risolvere prima i sottoproblemi, arrivando all'ultima cella in cui si troverร  la soluzione dell'intero problema.

Equazione di ricorrenza

DP[i][c]={0i=0ย orย c=0ย ย se non abbiamo piรน oggetti/capacitร max(DP[iโˆ’1][cโˆ’w[i]]+p[i]โžPreso,DP[iโˆ’1][c])โžNonย Presootherwise

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];
}

Knapsack.png600

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 k=โŒŠlogโกCโŒ‹ bit per rappresentare C, dunque la complessitร  รจ esponenziale rispetto al numero di bit dell'input.

Esempio:
Scegliamo come input i numeri che hanno 1 nel bit piรน significativo.
Input di 3 bit? โ†’ Input in decimale: 4
Input di 4 bit? โ†’ Input in decimale: 8
Input di 5 bit? โ†’ Input in decimale: 16
Input di 6 bit? โ†’ Input in decimale: 32

e cosรฌ via...

Quindi la complessitร  spaziale รจ O(nโ‹…2k), dove k=โŒŠlogโกCโŒ‹

Soluzione ricorsiva

Equazione di ricorrenza

T(n)={1nโ‰ค12T(nโˆ’1)+1n>1

Ovviamente non vale la pena scrivere un algoritmo ricorsivo, basato su divide-et-impera, per risolvere il problema, visto che la complessitร  sarebbe O(2n). Tuttavia, visto che รจ molto veloce da scrivere, ecco il codice per farlo.

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]
        );
}

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 DP prima di entrare in ricorsione a risolvere il sottoproblema. Questo metodo รจ chiamato memoization.

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:

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]
        );
    }
}

Memoization.png600

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 O(min(2n,ย nโ‹…C)).

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];
}

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ร  C e n oggetti caratterizzati da peso w e profitto p, definiamo DP[i][c] come il massimo profitto che puรฒ essere ottenuto dai primi iโ‰คn oggetti contenuti in uno zaino di capacitร  cโ‰คC, senza porre limiti al numero di volte che un oggetto puรฒ essere selezionato. Dunque il massimo profitto ottenibile dal problema originale รจ rappresentato da DP[n][C].

Soluzione ricorsiva con memoization

รˆ sufficiente non fare โˆ’1 ad i quando prendo l'oggetto, visto che posso prendere l'oggetto quante volte voglio.

Equazione di ricorrenza

DP[i][c]={0i=0ย orย c=0ย ย se non abbiamo piรน oggetti/capacitร max(DP[iโˆ’1][cโˆ’w[i]]+p[i]โžPreso,DP[iโˆ’1][c])โžNonย Presootherwise

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 DP.
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 c=0,1,2,...,C.

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];
}

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;
    }
}