Algorithmus, der das Array in Unterarrays aufteilt, wobei die maximale Summe aller Unterarrays so niedrig wie möglich ist
Nehmen wir an, wir haben ein Array von Ints: a = {2,4,3,5}
Und wir haben k = 3.
Wir können Array a in k (3) Unterarrays aufteilen, in denen die Reihenfolge des Arrays nicht geändert werden kann. Die Summe jedes Sub-Arrays muss so niedrig wie möglich sein, damit die maximale Summe aller Sub-Arrays so niedrig wie möglich ist.
Für die obige Lösung würde dies zu {2, 4}, {3}, {5} führen, was eine maximale Summe von 6 (4 + 2) ergibt.
Eine falsche Antwort wäre {2}, {4, 3}, {5}, da die maximale Summe in diesem Fall 7 (4 + 3) beträgt.
Ich habe versucht, einen gierigen Algorithmus zu erstellen, der den Durchschnitt des gesamten Arrays berechnet, indem alle Ints summiert und durch die resultierende Anzahl von Sub-Arrays dividiert werden. Im obigen Beispiel würde dies also 14/3 = 4 bedeuten (ganzzahlige Division). Es werden dann Zahlen zu einem Zähler addiert, solange er <als die durchschnittliche Zahl ist. Es wird dann für den Rest des Sub-Arrays neu berechnet.
Meine Lösung liefert eine gute Annäherung und kann als Heuristik verwendet werden, gibt mir aber nicht immer die richtige Antwort.
Kann mir jemand mit einem Algorithmus helfen, der mir für alle Fälle die optimale Lösung bietet und besser ist als O (N²)? Ich suche nach einem Algorithmus, der ungefähr 0 (n log n) ist.
Danke im Voraus