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