La dieta di Poldo Top Down

Ciao ragazzi, sto impazzendo. Non riesco a capire dove sbaglio nel problema “La dieta di Poldo”. Volevo provare a farlo in dinamica Top down e sono arrivato fin qui:

using namespace std;

int peso[10000];
int soluzioni[100000];
int mangiato;
int nonmangiato;
int N;
int precedente=10001;
int Panini(int panino)
{
    if(soluzioni[panino]!=-1)return soluzioni[panino];

    if(peso[panino]<precedente)
    {
        precedente=peso[panino];
        mangiato=1+Panini(panino+1);
    }
    nonmangiato = Panini(panino+1);

    if(mangiato>nonmangiato) {soluzioni[panino]=mangiato;return mangiato;}
    soluzioni[panino]=nonmangiato;return nonmangiato;
}

int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");

    in>>N;
    for(int i=0;i<N;i++)
        in >> peso[i];
    for(int i=0;i<1000;i++)
        soluzioni[i]=-1;
    soluzioni[N]=0;

    cout <<Panini(0);
    return 0;
}

Qualcuno può aiutarmi?(sto imparando da poco la programmazione dinamica)

Il problema sta che nel farlo in questo modo il valore di precedente è globale e quando lo vai a modificare prendendo un panino non ripristini in alcun modo il suo valore quando poi vai a considerare la soluzione nel caso in cui invece “non mangi”.

Ti consiglio di guardare la soluzione proposta nella guida del professor Bugatti o in alternativa di pensare al fatto che la tua funzione ricorsiva (e di conseguenza anche il tuo array che contiene le soluzioni già calcolate) ha bisogno di un parametro in più, ovvero della dimensione dell’ultimo panino mangiato :slight_smile:

1 Mi Piace

Ma se io mangio il panino 1 e poi salto il secondo, il precedente che ho mangiato sarà comunque il numero 1. Quindi dovrei confrontare quello attuale ovvero il 3° con il 1°(in caso accettassi di mangiare il 3°).
Oppure ho avuto una mezza idea di usare una matrice per le soluzioni in modo da avere la soluzione in base al precedente ma quando l’ho fatto mi dava output ancora più assurdi

Si ma tu mangi un panino per calcolare il risultato migliore se “mangi” e poi quando vai a vedere il risultato migliore se “non mangi” siccome chiami la funzione ricorsiva nel frattempo, il valore di precedente è diventato quello dell’ultimo panino che hai mangiato e quindi potrebbe essere un valore maggiore di quello del panino che tu stai decidendo di non mangiare. Comunque, per capire che è sbagliato ti basta immaginarti il caso di partenza, infatti se non prendi il primo panino dovresti avere scelta libera sul peso del secondo ma tu così lo vincoli comunque al peso del panino di partenza!

La soluzione con la matrice può funzionare, potresti ragionare su quella (o altrimenti passare all’approccio bottom-up che forse è più semplice in questo caso).