Ho tentato di risolvere questo problema con il classico metodo dello zaino, ma non riesco ha superare gli ultimi due task. Ho sbagliato approccio, o scrivo semplicemente male il codice?
L’approccio dovrebbe essere corretto. Magari il codice va solo leggermente modificato.
Su questo server non è sempre facile tenere sotto controllo i time limit dei task 
. Sul mio PC la tua soluzione gira in 0.55 secondi, mentre sul server richiede 1.5 secondi. Credo comunque che sia dovuto all’uso di un approccio top down (che ha in genere un overhead maggiore rispetto ad un approccio bottom up). Prova a riscrivere il codice con un approccio bottom up, ma tieni conto comunque che in genere il time limit in gara viene impostato in modo da far passare entrambi gli approcci, quando hanno la stessa complessità.
Sì, l’avevo implementata con un approccio top-down. Ok, l’ho risolto. Ma non mi è chiaro a cosa è dovuta la differenza di tempo se in teoria hanno la stessa complessità O(N*B)
Visto che esisteva già un topic a riguardo lo rilancio volentieri per chiedere un aiuto sul problema Menù giapponese. Sinceramente non capisco dove il mio codice non funziona, il correttore mi dice che prendo piatti non validi e siccome sono un po’ alle prime armi chiederei a qualcuno di più esperto se avesse voglia di dare provare a dirmi cosa non va. Ringrazio in anticipo.
const int MAXN = 5000, MAXK = 5000;
int memo[MAXN+1][MAXK+1];
int mangia(int N, int K, int P[]){
for (int i=0; i<=K; i++)
memo[0][i]=0;
for(int i=0; i<=N; i++)
memo[i][0]=0;
for(int i=1; i<=N; i++){
for(int j=1; j<=K; j++){
//se decido di non mangiarlo
memo[i][j]=memo[i-1][j];
// se lo mangio devo prima vedere che non sia più costoso del budget
if(P[i-1]<=j)
memo[i][j]=max(memo[i][j],memo[i-1][j-P[i-1]]+P[i-1]);
}
}
return memo[N][K];
}
int main() {
ifstream in("input.txt");
ofstream out("output.txt");
int N, K, P[5000], a, tot=0, J, b;
in >> N;
in >> K; //budget
for(int i=0; i<N; i++)
{
in >> P[i];
}
b=mangia(N, K, P);
out << b << endl;
}A prima vista mi sembra che il tuo programma risolva un problema leggermente diverso da quello richiesto dal testo 
Il tuo programma (se non erro) risponde alla domanda: “quanto riesco a spendere, al massimo, senza superare il budget?”
Il problema chiede invece: “qual è una possibile lista di costi (ovvero un sottinsieme del menù) tale che la somma dei costi è massima e non supera il budget?”
Le due domande sono simili, però la prima richiede un solo numero intero come risposta, mentre la seconda può avere tanti numeri interi come risposta. Ricontrolla il formato di output definito nel testo 
Già… Chiedo scusa per la domanda senza senso ma avevo letto il testo dell’esercizio qualche giorno fa e oggi nel provare a risolverlo non avevo più riletto le richieste perchè ero convinto che l’output dovesse essere la massima spesa possibile…
Nessun problema 