[RISOLTO] Ottimizzazione: Greedy Santa


#1

Come devo applicare la memoizzazione per ottimare il problema Greedy Santa.

Codice:

int greedy_santa(int gift[], int i, int sum)
{
    if(gift[i] + sum >= M)
    {
        return gift[i] + sum;
    }

    if(i == N)
        return 1000000;

    return  min(greedy_santa(gift, i+1, sum),greedy_santa(gift, i+1, sum+gift[i]));
}

Ps: se la funzione mi ritorna 1000000 vuol dire che dovrò stampare la somma di tutti i regali.


#2

Hai risolto giusto? Comunque dovrebbe essere facile.


#3

Si ho risolto. Ho commesso un errore stupido mentre scrivevo la soluzione dinamica.:sweat_smile: