Intervalleinteilung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:40 Mo 28.07.2008 | | Autor: | hoare |
Hallo,
mein Problem ist folgendes: Gegeben ist eine (sortierte) Folge von Zahlen bspw.:
1, 2, 2, 5, 5, 5, 5, 5, 6, 9, 10, 10
Dies möchte ich in n möglichst gleich große Gruppen aufteilen wobei keine Zahl gleichen Wertes in unterschiedlichen Gruppen auftreten darf.
Im oben genannten Beispiel wäre eine solche Aufteilung:
Gruppe A mit 1en und 2en
Gruppe B mit 5en
Gruppe C mit 6en 9en 10en
Gibt es einen Algorithmus mit dem ich das Problem in polynomieller Zeit lösen kann oder ggf. eine Heuristik?
Vielen Dank!
hoare
PS: Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
https://matheraum.de/read?i=431595
denke aber, dass sie hier besser aufgehoben ist.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:47 Mi 30.07.2008 | | Autor: | Stoecki |
Ich habe den verdacht, dass du das problem auf das partitionsproblem reduzieren kannst, welches ein np-problem ist. das partitionsproblem versucht auch zwei mengen in zwei gleichwertige aufzuteilen. du könntest hier jeder zahlengruppe den wert zuordnen, der die anzahl der elemente wiederspiegelt (also entspricht eine gruppierung 2, 2, 2 dem wert 3, da es 3 zweier gibt). diese müsstest du dann in gleichwertige gruppen einteilen. da schon das problem das in 2 gruppen aufzuteilen (bzw zu prüfen ob es geht) ein np-problem ist wird das andere das wahrscheinlich auch sein, wenn du versuchst möglichst große zu finden.
|
|
|
|
