Buonasera, avrei un problema con questo codice, ho utilizzato la programmazione dinamica come consigliato da AlgoBadge ma non riesco a trovare alcun bug. C’è un testcase in cui mi sbaglia l’output e un altro in cui supera il limite di tempo. Cosa potrei fare per migliorarlo?? Allego in seguito il codice.
#include <bits/stdc++.h>
using namespace std;
#define MAXP 1000005
int P[MAXP];
FILE *fr, *fw;
int mangia(int N, int K, int P[]) {
vector<int> dp(200001, INT_MAX); // vettore di supporto per la programmazione dinamica
dp[0] = 0; // inizializzazione
for (int i = 0; i < N; i++) {
for (int j = 200000 - P[i]; j >= 0; j--) { // scorriamo il vettore dp partendo da 200000 - P[i] per evitare di sovrascrivere dati utili
if (dp[j] != INT_MAX) { // se abbiamo gia' trovato una soluzione per il peso j, possiamo calcolare una soluzione per il peso j + P[i]
dp[j + P[i]] = min(dp[j + P[i]], dp[j] + 1);
}
}
}
for (int i = K; i <= 200000; i++) { // restituiamo il primo indice del vettore dp in cui abbiamo trovato una soluzione valida
if (dp[i] != INT_MAX) {
return i;
}
}
return -1; // se non abbiamo trovato soluzioni valide
}
int main() {
int N, K;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
for(int i=0; i<N; i++){
assert(1 == fscanf(fr, "%d", &P[i]));
}
fprintf(fw, "%d\n", mangia(N, K, P));
fclose(fr);
fclose(fw);
return 0;
}