Come sarebbe un algoritmo che divide / ordina i numeri in tre gruppi per renderli ugualmente grandi lavori?

Tieni traccia delle dimensioni di ciascuno dei sottogruppi e quando ce n'è uno che è ambiguo, posizionalo nel sottogruppo con il conteggio corrente più basso.

Se vuoi andare ancora più vicino, posiziona tutti i singleton nei rispettivi sottogruppi (tutti i valori non ambigui). E poi fai un secondo passaggio per tutto quello che rientra in 2 sottogruppi, e un terzo per tutto ciò che rientra in 3 sottogruppi, al massimo questa sarebbe comunque un'operazione O (n ^ 2), con quella precedente in esecuzione in O (n * log (n)) approssimativamente. Basandomi su quello che vedo nella mia testa.

Se dividi l'array principale in 3 sub-array con i valori di 1, 2 e 3 gruppi nei loro rispettivi array (se lo spazio non è un problema) puoi eseguire il secondo in quasi O (n * log (n)).

Penso che questo sia qualcosa sulla linea di un problema di copertura esatta . Almeno la soluzione dovrebbe essere possibile con approcci simili come Knuth ' Algorithm X e Link per il ballo .

È un tipo di Problema di soddisfazione dei vincoli o almeno simile ad esso. I tuoi vincoli qui sono le regole che i numeri devono soddisfare, appartenenti ad uno dei gruppi e i gruppi che si sommano il più possibile simili.

Potresti risolvere questo problema con una specie di Prima ricerca sulla profondità , poiché devi confrontare tutti i risultati (anche se potresti interrompi la ricerca nel caso in cui trovi un raggruppamento in cui tutti i gruppi abbiano somme esattamente uguali e non riescano a migliorare)

Primo passo: assegna quei numeri che possono appartenere solo a un singolo gruppo e dimenticatene.

Quindi prendi il primo numero che ha due opzioni. Scegli la prima opzione e procedi con il prossimo numero allo stesso modo. Ripeti fino a quando tutti i numeri sono assegnati e ricorda le somme dei gruppi.

Quindi tornare indietro di un passo con l'ultimo numero e assegnare il numero al successivo gruppo possibile. Se questo era l'ultimo gruppo possibile, torna indietro di un altro numero, assegna questo al successivo gruppo possibile e procedi di nuovo con l'ultimo numero.

In questo modo ottieni un albero di ricerca che attraversa tutte le possibili combinazioni.

Anche se questo userebbe molta memoria nel caso abbiate molti numeri.

(In questo caso non è un problema di copertura esatto , poiché non esiste necessariamente una soluzione esatta.)