Pranzo della nonna

Aiuto
1

ciao sono alle prime armi con la programmazione dinamica ed è da 2 giorni che provo a risolvere questo problema non capendo perché in alcuni testcase va in altri no e in altri fa timed out, grazie in anticipo per l’aiuto

#include <stdio.h>
#include <assert.h>
#include
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
int N,K;
int P[MAXN];

int f(int p,int i,int v)
{
if(i==N)
return p;
int a,b;
a=f(p,i+1,v);
b=f(p-v[i],i+1,v);
if(abs(K-a)<abs(K-b))
return a;
else
return b;
}

int main() {
FILE *fr, *fw;
int i;

fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
for(i=0; i<N; i++)
    assert(1 == fscanf(fr, "%d", &P[i]));

fprintf(fw, "%d\n", f(K,0,P));
fclose(fr);
fclose(fw);
return 0;

}

2

Mi sembra di vedere che hai utilizzato la ricorsione nel tuo codice, e credo che si trovi esattamente li il problema.

Sono convinto che faccia timed out perché fa troppi passaggi e ci mette semplicemente troppo.
Il mio consiglio è quello di provare a utilizzare il problema dello zaino (knapsack) che dovrebbe non solo riuscire a risolvere il tuo problema dei casi sbagliati ma anche il problema del timed out.

Del knapsack esistono diverse varianti, ti consiglio di usare la variante che usa 2 array, o se ti senti coraggioso e hai in mente come farlo puoi anche fare quella con un solo array per usare ancora meno memoria.