Nonna (DP) Aiuto

Aiuto
1

Buongiorno! Da qualche giorno ormai sono incartato sul problema “Nonna”, che voglio risolvere mediante programmazione dinamica.
Prima di lanciarmi in questo problema ho “studiato” knapsack 0-1 e largest common subsequence, faccio comunque difficoltá ad applicare il loro approccio a questo problema, siccome mi ritrovo sempre con 0 o MAXP in output. Chiedo aiuto, questo é il codice scritto finora

int mangia(int N, int K, int P[]) {
    int dp[N+1][K+1];
    
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            if (i == 0 || j == 0){
                dp[i][j] = 0;
            }
            else if(P[i] > j){
                dp[i][j] = dp[i-1][j];
            } 
            else{
                dp[i][j] = min(dp[i-1][j], P[i-1] + dp[i-1][j-P[i-1]]);
            }
        }
    }
    
    return dp[N][K];
}
2

Sei sicuro che quando il valore è maggiore della capienza attuale tu stia facendo la scelta giusta?

3

Grazie per la risposta!
Faccio comunque ancora fatica a capire cosa dovrei fare in questa situazione dal momento che se P[i] è maggiore di j dovrei usare la “soluzione precedente”, non mi è ancora chiaro se sia dp[i-1][j] o dp[i][j-1]- ma credo che il problema stia addirittura nel modo in cui inizializzo la matrice.
Allego uno schema che ho fatto nel tentativo di capirci qualcosa. Grazie ancora.

Immagine
Immagine1580×752 16.9 KB