Kombination aus einem Array von Zahlen

[NoXeno]

Hallo erstmal..

..ich hab da ein kleines Problemchen..
Ein Array mit 50 Zahlen und eine Summe sind gegeben. Die Summe setzt sich aus einer unbekannten Anzahl von den 50 Zahlen zusammen. Diese Kombination soll ermittelt werden.. ..wie geht man das am besten an?

Danke für Eure Zusammenarbeit!

[dizzy]

Jedes Array-Element := Summe/50

Oder nur Integer? Jeden Summanden nur ein mal verwenden? Müssen ALLE 50 Summanden <> 0 sein? Dürfen Summanden auch < 0 sein? Gehts um Primzahlzerlegung?

...rück mal ein paar Infos raus. Es gibt 1001 möglichkeiten einn Wert auf 50 Summanden zurückzuführen.


gruss,
dizzy

[NoXeno]

nepp.. jeder Summand darf nur einmal verwendet werden, aber es kann auch gleiche Summanden geben
jepp.. alle Summanden sind ungleich 0
jepp.. Summanden dürfen auch kleiner 0 sein

Beispiel:
-35,00
-24,99
-7,28
2,73
20,44
30,45
48,16
58,17
75,88
85,89
103,60
113,61
131,32
141,33
159,04
169,05
186,76
196,77
214,48
224,49
242,20
252,21
269,92
279,93
297,64
307,65
325,36
335,37
353,08
363,09
380,80
390,81
408,52
418,53
436,24
446,25
463,96
473,97
491,68
501,69
519,40
529,41
547,12
557,13
574,84
584,85
602,56
612,57
630,28
630,28
^^^^^^
gegebene Zahlen

9.161,46 ist die gesuchte Summe, die sich irgendwie aus diesen Zahlen zusammensetzt
..es soll nur eine Möglichkeit gefunden werden


reicht das erstmal?

[Luckie]

Das Stcihwort hier, dürfte wohl Kombinatorik bzw. Permutation (ich weiß nie, was was ist. ) sein.

[NoXeno]

mhm.. zu kompliziert?!?

[hummer]

Muss sich die Summe denn aus den gegebenen Zahlen zusammensetzen können? Oder ist es auch möglich, dass es keine Kombination geht?

[NoXeno]

in dem obigen Beispiel ist es möglich und es soll auch generell so sein..

[dizzy]

Achsooooo es sind auch die Summanden vorgegeben. Ich dachte, du sollst selber ein Set von Summanden zu deiner gegeben Summe angeben...

In diesem Fall würde ich mit Bruteforce dran gehen. Also einfach ALLE Kombinationen durchtesten, und die die gehen merken.
Man kann vielleicht auch was performanteres machen, aber mir ist spontan nichts bekannt.
Der Rechenufwand ist glücklicherweise recht gering. Es sind keine Permutationen (dort werden alle Möglichkeiten auch mit Vertauschung gebildet, denn Addition ist so schön kommutativ, da brauchts das nicht (a+b = b+a)), bei denen der Aufwand fakultätisch wäre, aber ein qudratischer aufwand ist es. Also müsstest du 50² (=2500) Kombinationen abprüfen. Das geht gut!

(Bei der gleichen Aufgabe mit Divisionen wäre es schon heftiger, weil nicht kommutativ. Da wären es mal locker 3,0414093201713378043612608166065e+64 = (ca.) 30.414.093.201.713.378.043.612.608.166.065.000.000 .000.000.000.000.000.000.000.000.000 Kombinationen (weil echte Permutation nötig), aber auch nur dann, wenn ALLE Werte mitspielen sollen. Wenn welche weggelassen werden können, dann wirds erst recht ungemütlich. Dann sind es 1!+2!+3!+4!+5!+6!+7!+8!+9!+....+49!+50!)
Prost


gruss,
dizzy

[tobster]

Rucksackproblem