Aiuto per Dividi i piatti (sortilegio_pasti)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Dividi i piatti.

Ho provato a creare un programma Greedy: inizialmente ordina il vettore in modo decrescente, e poi inizia a dare i valori alla parte che ne ha meno, ma questo non funziona nel substack 3 e 4.

Ecco il mio codice:

int dividi(int N, vector<int> V) {
    sort(V.begin(), V.end());
    reverse(V.begin(), V.end());

    int somma = 0;

    for (int val:V){
        if (somma >= 0) somma -= val;
        else somma += val;
    }

    return abs(somma);
}

Credo che il mio sia un errore di logica ma non capivo dove era sbagliato.
Quindi volevo chiedere se era solubile con il greedy, o era neccesario usare il DP

Grazie mille in anticipo!

2

Ad occhio il problema sembra NP-Hard, e quindi dubito che si possa risolvere con una greedy.
un esempio per il quale la tua soluzione non funziona: 5 4 3 3 3

1 Mi Piace
3

Non basta una greedy, puoi provare a trovare una DP.
Confermo che il problema non eā€™ NP, dato che bisogna scegliere tutti i piatti per creare una divisione valida.