Come partizionare una matrice di numeri interi in modo da minimizzare il massimo della somma di ciascuna partizione?

Question

Gli input sono un array A di interi positivi o nulli e un altro intero K.

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

Answer 1

Utilizzare la ricerca binaria.

Lasciare un intervallo di somma massimo da 0 a somma (matrice). Quindi, mid = (range/2). Verifica se è possibile raggiungere mid mediante il partizionamento nei set k in O (n). Se sì, vai per un raggio più basso e se no, vai per un raggio più alto.

Ciò fornirà il risultato in O (n log n).

PS: se hai qualche problema con la scrittura del codice, posso aiutarti ma ti suggerisco di provare prima tu stesso.

EDIT:
come richiesto, ti spiego come trovare se mid può essere raggiunto mediante suddivisione in gruppi k in O (n).
Iterate attraverso gli elementi finché la somma è inferiore o uguale a mid. Appena diventa maggiore di mid, lascia che faccia parte del prossimo set. Se ottieni k o meno set, è possibile ottenere mid, altrimenti no.