Zwei Mengen mit der niedrigsten Differenz zueinander bestimmen. |
| 27.04.2018, 01:16 | Polo85 | Auf diesen Beitrag antworten » | ||
| Zwei Mengen mit der niedrigsten Differenz zueinander bestimmen. ich möchte gerne einen Algorithmus umsetzen, der folgende Kriterien erfüllt: 1a) Ich habe eine Hauptmenge bestehend aus mindestens zwei Elementen und maximal 8 Elementen. 1b) Jedes Element ist eine natürliche Zahl und größer als Null. Es sollen aus dieser Hauptmenge genau zwei neue Mengen gebildet werden: 2a) beide neuen Menge(a und b) besitzen mindestens ein Element aus der Hauptmenge, bzw. wenn Menge a genau ein Element aus der Hauptmenge aufnimmt, müssen die restlichen Elemente aus der Hauptmenge auf die Menge b abgelegt werden oder anders herum. Also alle Elemente aus der Hauptmenge werden vollständig auf beide Mengen abgelegt ohne Wiederholungen. Das Wie bisher: Die Verteilung der Elemente auf a und b folgt anhand ihrer niedrigsten Differenz der beiden Mengen zueinander. Beispiel: Hauptmenge = {105,100,75,55,41,40,19} a={105,55,41} Summe= 201+19 = 220 b={100,75,40} Summe= 215 a - b = 220-215 =5 Die Hauptmenge habe ich vorher absteigend sortiert und dann abwechselnd auf a und b verteilt. Die Differenz ist aber nicht die kleinste zueinander. Denn: a={100,75,41} Summe = 216 b={105,55,40} Summe = 200+19 = 219 a-b = 216-219=-3 =|3| Durch probieren habe ich das heraus gefunden. Um das umzusetzen, müsste ich jetzt eine Schleife programmieren die alle Kombinationen für die Elemente der Hauptmenge auf a und b durchgeht und die Differenz ermittelt und dann die niedrigste findet. Wenn ich mich nicht täusche sind das bei 8 Elementen, 8! / a!*b!. Da aber a und b varieren ergibt das 70+56+28+8 Kombinationen, das ist zwar lächerlich wenig, nur habe ich die Hoffnung das weniger umständlich durch eine Schleife zu lösen die alles vergleicht. Kann ich die Elemente schon vorher irgendwie sortieren in der Hauptmenge damit eine Verteilung auf a und b erfolgt anhand der niedrigsten Differenz zueinander? |
||||
| 27.04.2018, 05:49 | IfindU | Auf diesen Beitrag antworten » | ||
| RE: Zwei Mengen mit der niedrigsten Differenz zueinander bestimmen. Das Problem ist ein intensiv erforschtes des Diskreten Mathematik wiki. Da es NP vollständig ist, ist keine einfache, schnelle "systematisch" Lösung bekannt. Einfaches Sortieren der Grundmenge wird nicht reichen. |
||||
| 27.04.2018, 08:44 | Polo85 | Auf diesen Beitrag antworten » | ||
RE: Zwei Mengen mit der niedrigsten Differenz zueinander bestimmen.
Danke dir vielmals. Du bist der erste der mein Problem einen Namen geben kann. Die ganzen Programmierer aus meinem Forum wussten ebenfalls keine Lösung. Noch nie von gehört, das Partitionsproblem. Dachte bisher mein Problem wäre trivialer. 
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
