# Gibt es eine Algorithmus dafür???



## jonas.r (28. Nov 2013)

Hey ihr!
Für meine App brauche ich einen Algorithmus der folgendes macht:
Es gibt n-Boxen welche jeweils die Elemente A, B, C und D in sich tragen. Jedes dieser Elemente hat ein Gewicht. Nun soll eine Kombination von *zwei* Boxen ermittelt werden, die von den beiden Boxen jeweils das kleinste A, B, C und D heraus sucht und in eine neue Box tut. Von diesen Boxen brauche ich die, mit dem niedrigsten Gewicht.

Also ich habe die Boxen:
1.: A=1, B=2, C=7, D=3
2.: A=5, B=10, C=1, D=7
3.: A=1, B=3, C=6, D=2

Das einzige was mir jetzt einfällt, wäre jede Kombination aus 2 Boxen heraus zu finden, von diesen beiden Boxen jeweils A1 uns A2 zu vergleichen und dann das kleinste in die neue Box zu tun. Und das mit allen 4 Elementen. Also würden sich folgende Boxen ergeben:

1.(Aus 1&2): A=A1(1) , B=B1(2), C=C2(1), D=D1(3) = 7
2.(Aus 1&3): A=A1(1), B=A1(2), C=C3(6), D=D3(2) = 11
3.(Aus 2&3): A=A3(1), B=B3(3), C=A1(1), D=D3(2) = 7

Die 1. Kombination würde nun ausgewählt werden.

Doch wenn ich nun 5 Boxen habe gibt es schon 10 verschiedene Kombinationen und wenn ich 6 Boxen habe schon 15 verschiedene Kombinationen. Geschweige denn, wie viele Vergleiche zwischen den Elementen gezogen werden müssen, wenn es nicht nur 4, sondern 20 gibt.

Also, gibt es eine bessere Lösung für das Problem? Kann man das Eventuell mit einem Graphen lösen?

Danke schonmal, wenn du es bis hier geschafft hast, ich würde mich sehr über deine Hilfe und Anregungen freuen!

Liebe Grüße,
Jonas


----------



## klauskarambulut (29. Nov 2013)

Ja, gibt es.

Man berechne die Extremwerte der Boxen und eliminiere die Irrelevanten.

Danach vereinige man zwei Boxen berechne die Extrema und eliminiere weitere Irrelevante.

Danach vereinige man zwei weitere Boxen berechne die Extrema und eliminiere weitere Irrelevante.

Etc.


----------



## jonas.r (29. Nov 2013)

Viele Dank, für deine Antwort, aber so ganz versteh ich nicht was du meinst 
Was sind denn die Extremwerte von 2 Boxen? 
Was sind dann die Irrelevanten? 
Wie weiß ich nun, welches Boxen-Paar das "günstigste" ist?

Wenn ich nun will, dass für eine neue Box nicht nur 2, sondern z.B. 3, oder 4 Boxen geöffnet und miteinander verglichen werden dürfen, wie würde das dann aussehen?
Also, ich denke, es reicht, wenn du mir die ersten 3 Fragen beantwortest, auf die 4. komme ich bestimmt von selbst=)

Liebe Grüße,

Jonas


----------



## klauskarambulut (29. Nov 2013)

Was sind denn die Extremwerte von 2 Boxen? 

Die Extremwerte sind das Minimum und Maximum.
Box1: 1; 7
Box2: 1;10
Box3: 1; 6

Was sind dann die Irrelevanten? 

Irrelevant ist eine 
Box4: 7; 7

Wie weiß ich nun, welches Boxen-Paar das "günstigste" ist?

Kombiniert man nun 1 und 2 erhält man (1, 2, 1, 3 )
Box1_2: 1; 3

Box5: 3; 3 ist irrelevant.


Desweiteren kann eine Sortierung im Voraus helfen, nach der

Summe der Wurzeln

A1: sq(1) + sq(2) + sq(1) + sq(7)



Außerdem kann es noch helfen, wenn eine Spalte überall den selben Wert hat, diese nicht mehr zu berücksichtigen.


----------



## jonas.r (1. Dez 2013)

Hey,
viele Dank für deine Zeit und die Antwort!
Tut mir Leid, dass ich so viele Fragen stelle ???:L

Gibt es zufällig eine Namen für diesen Algorithmus oder für diese Problemstellung?, dann könnte ich ggf. selber weiter recherchieren. 

Man betrachtet also immer nur die Extremwerte, um zu wissen, was für eine Kombination die Beste ist. Habe ich das richtig verstanden?

Man stelle sich vor ich habe folgende 3 Boxen:
Box-1: 1; 2; 5 -> 1; 5
Box-2: 2; 2; 2 -> 2; 2 ->irrelevant?
Box-3: 4; 2; 3 -> 2; 4

Dann wäre doch die günstigste Lösung das erste (und das 2.) Element aus Box-1 und das 3. aus Box-2 zu nehmen. Wenn jetzt aber Box-2 irrelevant sein soll (also nicht mehr berücksichtigt werden würde), würde doch das Ergebnis sein, dass Box1_3 (Gewicht=6) rauskommen würde, was insgesamt ein höheres Gewicht als Box1_2 (Gewicht=5) hätte.

Deswegen verstehe ich das nicht so ganz :/

Liebe Grüße,

Jonas


----------



## jonas.r (2. Dez 2013)

Keine Antwort? Mir reicht wirklich auch der Name des Algorithmus.


----------

