Gli input sono un array A di interi positivi o nulli e un altro intero K.Come partizionare una matrice di numeri interi in modo da minimizzare il massimo della somma di ciascuna partizione?
Dobbiamo partizionare A in blocchi K di elementi consecutivi (per "partizione" intendo che ogni elemento di A appartiene a qualche blocco e 2 i diversi blocchi non contengono alcun elemento in comune).
Definiamo la somma di un blocco come somma degli elementi del blocco.
L'obiettivo è trovare una partizione di questo tipo in blocchi K in modo tale che il massimo delle somme di ogni blocco (chiamiamolo "MaxSumBlock") sia ridotto a icona.
Dobbiamo uscita il MaxSumBlock (non abbiamo bisogno di trovare una partizione reale)
Ecco un esempio:
ingresso:
A = {2, 1, 5, 1, 2, 2, 2}
K = 3
uscita prevista:
MaxSumBlock: 6
(with partition: {2, 1}, {5, 1}, {2, 2, 2})
Nell'output previsto, le somme di ogni blocco sono 3, 6 e 6. Il numero massimo è 6.
Ecco una partizione non ottimale:
partition: {2, 1}, {5}, {1, 2, 2, 2}
Le somme di ciascun blocco in questo caso sono 3, 6 e 7. Il massimo è quindi 7. Non è una risposta corretta.
Quale algoritmo risolve questo problema?
MODIFICA: K e la dimensione di A non è superiore a 100'000. Ogni elemento di A non è maggiore di 10'000
Quali sono i vincoli sulla dimensione della matrice e K? –
Ho appena modificato la mia domanda – Brainless
Programmazione dinamica (con aumento di A e K)? –