Pranzo dalla Nonna LTE

Aiuto
1

Potreste dirmi come potrei ottimizzare il programma?

#include <bits/stdc++.h>

using namespace std;

#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000

int dp[MAXN + 1][MAXK + 1];

int mangia(int i, int w, int P[]) {
    int ans = INT_MAX;
    if (i <= 0 || w <= 0)
        return 0;
    if (dp[i][w] != -1)
        return dp[i][w];
    for (int j = 1; j <= i; j++) {
        int temp = P[i - j] + mangia(i - j, w - P[i - j], P);
        if (w <= temp)
            ans = min(ans, temp);
    }
    dp[i][w] = ans;
    return ans;
}


int P[MAXN];

int main() {
    FILE *fr, *fw;
    int N, K, 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]));


    for (int row = 0; row < N + 1; row++) {
        for (int col = 0; col < K + 1; col++) {
            dp[row][col] = -1;
        }
    }

    fprintf(fw, "%d\n", mangia(N, K, P));
    fclose(fr);
    fclose(fw);
    return 0;
}
2

Ciao, la tua funzione ricorsiva per trovare la risposta al task è un po’ troppo lenta dovresti, invece, impostarla tipo mangiare/NON mangiare la portata P[i]:

dp[i][w] = min(mangia(i+1, w+P[i], P[]), mangia(i+1, w, P[]));

Altrimenti con la tua soluzione per rientrare nel TLE è sufficiente ordinare le portate P[i] e prendere in considerazione solo le prime n tale che:

P[0] + P[i] + ... + P[n] < 2*K.
1 Mi Piace