Erkennen von Zahlenpaaren

[lowmax_5]

Folgende Problematik stellt sich:

Eingabe:

1. Geben sind zwei Mengen von Zahlenpaaren
   
2. Die Summe der Menge 1 ist gleich der Summe von Menge2
   
3. Es sollen nun Kombinationen zusammengestellt werden
   
4. Menge1: (2,6,7,1,6,15,7,4,1) ==> Summe 49
   
5. Menge2 (16,13,9,11) ==> Summe 49

Ausgabe:

1. Welche Zahlen ergeben welche Summen? z.b. (16==>15+1) + (13==>7+6) + (9=>2+6+1) + (11=>7+4)
   
2. Ist Ergebis eindeutig oder gibt es mehrere Kombinationsmöglichkeiten?
   
3. Gesucht ist die Lösung mit den besten Kombinationen (Möglichst kurz)

Wie kann ein Lösungansatz aussehen? Bin für jeden Tipp dankbar!

[Zacherl]

Falls es da nicht irgendeine ausgefeilte mathematische Herangehensweise gibt, die mir unbekannt ist, würde ich auf Bruteforce (Erzeugen sämtlicher Permutationen) zurückgreifen. Soll es möglichst performant sein, kannst du auch Backtracking verwenden.

[lowmax_5]

Zitat:

...Soll es möglichst performant sein...

... Alles was unter einer Sekunde ist, ist akzeptabel!

[JasonDX]

Zitat von lowmax_5:

Zitat:

...Soll es möglichst performant sein...

... Alles was unter einer Sekunde ist, ist akzeptabel!

Für welche Eingabegröße? 10 Zahlen, 100, 1000, 1000000?

Wenn ich mich nicht ganz täusche, ist das Problem NP-vollständig, d.h. eine "einfache, schnelle" Lösung gibts nicht. Brute-Force ist die wahrscheinlich einfachste Variante, die für kleine Mengen auch kein Problem darstellen sollte.

[lowmax_5]

Zitat:

Für welche Eingabegröße? 10 Zahlen, 100, 1000, 1000000?

Bis 1000 reicht in diesem Fall aus.

[BUG]

Mhm, auf den ersten Blick sah es nach Partition aus, allerdings scheinst du ja eine passende Partition zu haben.
EDIT: JasonDX hat recht; das Partitionsproblem sollte sich darauf reduzieren lassen. Eingabe von Partition wird M1, M2 hat zwei Elemente: jeweils die Hälfte der Summe aller Elemente in M1.

Ich verstehe das Problem so: finde für jedes Element aus Menge2 eine Summe aus Elementen aus Menge1, sodass kein Element aus Menge1 doppelt verwendet wird (?)

Klar ist, dass dann immer alle Elemente von Menge1 benutzt werden müssen, da die Summe der Elemente gleich ist. Was heißt also ein "kurzes Ergebnis"?

Es gibt nicht immer ein Ergebnis. Beispiel:
M1 = 2, 4, 6
M2 = 3, 9

Es kann unterschiedliche Ergebnisse geben (welches ist hier besser/kürzer?):
M1 = 1, 2, 2, 3
M2 = 5, 3
5 = 1 + 2 + 2 und 3 = 3
5 = 2 + 3 und 3 = 2 + 1