Aiuto "Pranzo della nonna" 10/100 (nonna)

Aiuto
1

Buonasera a tutti, é da qualche ora che provo a risolvere questo problema, pensavo di averlo implementato correttamente ma mi da qualche errore sporadico un po su tutti i test (immagino che nel caso di un certo input il mio programma semplicemente fallisca).

Ecco il mio codice:

#include <stdio.h>
#include <assert.h>
#include <algorithm>

using namespace std;

int mangia(int N, int K, int P[]) {
    // 0 Se ho un solo elemento, beh quello sará la risposta
    if (N == 1) return P[0];

    // 1 Se dopo aver ordinato i pesi, quello piú piccolo é >= K allora é la risposta
    sort(P, P + N);
    if (P[0] >= K) return P[0];

    // 2 Se ho un singolo minore elemento < K allora la risposta é P[1]
    if (P[1] >= K) return P[1];

    // 3 La soluzione é una combinazione di pesi ??
    int smallestPnearK = -1;

    for (int i = 0; i < N; ++i) {
        if (P[i] == K) return K;
        if (P[i] > K) {
            smallestPnearK = P[i];
            break; // Visto che P é ordinato, é il primo elemento che supera K
        }
    }

    // TODO: Codice solo delle combinazioni < K
    int M = (2 * K); // Piccolo dubbio 2K-1
    int mem[N][M];

    // Setup
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (i == 0 || j == 0) mem[i][j] = 0;
            else mem[i][j] = -1;

    // Praticamente l'algoritmo di Knapsack
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < M; ++j) {
            if (j - P[i] >= 0)
                mem[i][j] = max(mem[i - 1][j], mem[i - 1][j - P[i]] + P[i]);
            else
                mem[i][j] = mem[i - 1][j];
        }
    }

    // Troviamo la somma del migliore set
    int sommaDelMiglioreSet = -1;
    for (int i = 0; i < N; ++i) {
        if (sommaDelMiglioreSet != -1) break;

        for (int j = 0; j < M; ++j)
            if (mem[i][j] >= K) {
                sommaDelMiglioreSet = mem[i][j];
                break;
            }
    }

    if (smallestPnearK == -1) {
        if (sommaDelMiglioreSet == -1) {
            sommaDelMiglioreSet = 0;
            for (int i = 0; i < N; ++i) {
                sommaDelMiglioreSet += P[i];
            }
        }
        return sommaDelMiglioreSet;
    } else {
        // 4 La soluzione é o una combinazione di pesi < K oppure il peso piú piccolo > K
        return min(sommaDelMiglioreSet, smallestPnearK);
    }
}


int main() {
    int N, K, i;

    FILE *fr, *fw;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(2 == fscanf(fr, "%d %d", &N, &K));

    int P[N];

    for(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;
}

Esempio risultato della sottomissione:
es

Grazie in anticipo a chiunque risponda…