Buongiorno a tutti, ho un problema con l’esercizio Medaglie.
Questo è il nucleo ricorsivo per l’algoritmo che dovrebbe risolvere il problema.
Il problema delle prestazioni esponenziali e delle occupazioni dello stack eccessiva è già noto ed esite già una versione ottimizzata che condivide gli stessi problemi di base.
L’algoritmo risolve il primo set senza alcun problema, e 4 del secondo.
int best_choice(int L, long long int* V){
if(L>=3)return V[0]-min3(best_choice(L-1,V+1),best_choice(L-2,V+2),best_choice(L-3,V+3));
else if(L==2)return V[0]-min2(best_choice(L-1,V+1),best_choice(L-2,V+2));
else if(L==1)return V[0]-best_choice(L-1,V+1);
else return 0;
}
min3 è una funzione che restituisce il minore tra tre numeri e min2 fra due.
L è il numero di celle dell’array ancora da processare, mentre V contiene l’integrale dell’array di partenza.
La lettura del file e la popolazione degli array avviene come in seguito:
FILE *fr, *fw;
int N, i;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(1 == fscanf(fr, "%d", &N));
for(i=0; i<N; i++)
assert(1 == fscanf(fr, "%d", &array[N-1-i]));
for(int i=0;i!=N+1;i++)support[i]=-1;
arrayI[N]=0;
for(int i=1;i!=N+1;i++){arrayI[N+1-i-1]=arrayI[N+1-i]+(array[i-1]*2+1)*100;}
for(int i=N-1;i>0;i-=1)best_choice_l(N-i,arrayI+1+i,support+i);
int test=best_choice_l(N,arrayI+1,support);
fprintf(fw, "%d\n", (int)(arrayI[0]-test));
Grazie per l’attenzione e buona giornata.
.