Tool zum Matchen von Zahlen, um auf Zielwert zu kommen

[Cool Master]

Zur Vereinfachung könnte man auch sagen, dass die erste passende Lösung reicht und das Programm da stoppt.

Na das ist aber was völlig anderes und deutlich leichter als alles zu überprüfen

 

[andy_m4]

Selbst wenn ich beruflich nutzen würde: ich suche nach eine fertigen Lösung und möchte nichts programmieren lassen.

Keine Ahnung ob es dafür ein fertiges Tool gibt, weil das ein eher spezielles Problem ist. Ich denke, man wird ums programmieren (lassen) nicht drum herum kommen. Immerhin wurden ja schon einige Lösungsansätze aufgezeigt. Es ist ja nicht so, dass man bei Null anfangen muss.

Oder zählt der Hinweis "Benutz dafür Tool xy." auch schon als Consulting und wird mit dem aktuell gültigen Tagessatz des Forum-Benutzers berechnet?

Ich glaube, es geht einfach nur um die Sorge, das jemand sich quasi kostenlos mit der Arbeit anderer bereichern möchte. So nach dem Motto: "Frag ich mal die Trottel im Forum".

Lächerlich, auf welche Ideen Leute teilweise kommen. Früher war ein Forum da, um eine Frage zu stellen und dazu eine Hilfestellung zu bekommen. Heutzutage hat jeder was zu kacken.

Genau. Früher war alles besser. Du musst aber auch bedenken, dieses Forum ist eine freiwillige Veranstaltung. Du hast keinen Anspruch darauf hier ne Lösung zu bekommen. Wenn Du das möchtest, wende Dich an die betreffende (zumeist kostenpflichtige) Stelle.

Der Ton macht die Musik. Solange jemandem vorgeworfen wird, dass er sein Problem abstrahiert darstellt und zu blöd ist, seine Problemstellung zu erläutern, gehe ich darauf auch nicht ein.

Zunächst einmal willst Du etwas von den Leuten hier. Hier ist sicherlich keiner da der auf nix anderes wartet als Dir möglichst zu helfen. Dementsprechend wäre es da nicht verkehrt mit ein bisschen mehr Demut aufzutreten.

Und übrigens, solche Sachen ob doppelte Einträge eliminiert werden dürfen oder nicht macht durchaus ein Unterschied. Sowohl was die Aufgabenstellung angeht als auch die Lösung. Solche Infos vorher zu wissen, ist da äußerst hilfreich.
Und ist dann klar, wenn sich da jemand die Mühe(!) macht sich etwas zu überlegen und hinterher kommt dann raus, dass der Ansatz völlig falsch war, weil Du Informationen (wenn auch unabsichtlich) unterschlagen hast, kann ich verstehen wenn da jemand etwas ungehalten reagiert.

Was halt oft im Forum passiert ist, das jemand irgendwie ne Frage hinklatscht ohne sich vorher Gedanken darum zu machen die Frage möglichst präzise zu stellen und die Antworter sollen sehen, wie sie damit klar kommen. Sprich der Fragesteller investiert kaum Zeit und Gehirnschmalz und erwartet das aber implizit von denen, die ihn helfen.

Das ist sicherlich auch der Grund für eine "Grundgenervtheit". Und wenn da irgendwie unpräzise Fragestellungen kommen, dann kann die sich auch mal entladen. Aber deswegen muss man nicht gleich rumheulen a-la "der Ton macht die Musik" und dann bockig den Rest des Beitrages ignorieren. Wie gesagt. Du willst etwas. Nicht umgekehrt.

Zumal dazu kommt, dass ständig von "Millionen Lösungen" gesprochen wird. Woher kommt diese Annahme? Bei den Beispielwerten (nimmt man - wie besprochen - die doppelten raus) wird es - wenn überhaupt - nur eine Lösung geben, sonst keine.

Trotzdem muss es ja irgendeine Vorgehensweise geben, falls es doch mal mehr als eine Lösung gibt. Wenn Du sagst, Dich interessiert nur eine, dann ist es eben so. Nur muss man das eben wissen.

Gruß
Andy

 

[Miuwa]

[-- Sorry, Doppelpost --]

Ich werd meinen Code heute oder morgen mal raussuchen -- ich kann aber nicht sagen, wann ich wieder gelegenheit habe den Computer rechnen zu lassen.

Die für mich entscheidende Sache: Wenn du weißt, dass deine Zahlen max 1 Lösung ergeben, dann muss es dafür ja einen Grund geben. Wenn man diesen Grund kennt könnte man potentiell einen Algorithmus schreiben, der sich das zu Nutze macht und das Ergebnis schneller findet.

Davon abgesehen muss man generell eben nicht alle möglichen Kombinationen durchprobieren. Als Beispiel:
Wenn man z.B. bereits genug von den größten Zahlen ausgewählt hat, dann wird man nie auf das passende Ergebnis kommen, egal welche anderen Zahlen man noch dazu nimmt. Das gleiche gilt für Kombinationen die keine der größten Zahlen enthalten. Ob das den Lösungsraum jetzt massiv einschränkt oder nicht hängt halt von den konkreten Zahlen ab.

Tut mir übrigens leid, wenn mein damaliger Post zu aggressiv rüber kam - war zu dem Zeitpunkt wegen was anderem gefrustet.

 

[andy_m4]

Und nochmal: es ist völlig egal, ob es keine, eine oder mehrere Lösungen gibt. Er muss trotzdem schlechtestenfalls alle Kombinationen prüfen.

Ja. Aber man kann trotzdem Optimierungen einbauen, in dem man mögliche Kombinationen die "nicht vielversprechend" aussehen nicht oder erst später überprüft (das würde man nicht einbauen, wenn man sowieso alle Lösungen braucht).

Wie schon mehrfach im Thread angedeutet haben wir hier ein (massives) Laufzeitproblem. Wenn Du alle Lösungen durchspielen musst, hast Du in der Regel (natürlich je nachdem wieviele Werte es sind) eh verloren.
Aber ärgerlich kann es auch dann sein, wenn die Berechnung mehrere Stunden dauert. Brauchst Du das Tool 5 Mal am Tag ist es halt Asche wenn man da ewig auf ne Lösung warten muss.

Für solche Optimierungen kann es auch hilfreich sein zu wissen, wie die Zahlen beschaffen sind oder/und auch, in welchem Bereich die sich bewegen.

Gruß
Andy

 

[schmidt206]

Das Forum ist ja dafür da, damit man darüber redet.
Ich hatte ja auch nicht nach einer Lösung gesucht, die anders arbeitet, als die jetzige, die ich benutze (welche einfach alle Zahlen miteinander kombiniert und keine weiteren Abbruchbedingungen hat), sondern nach einer optimierten (sprich: modernen) Lösung.
Dass dabei das Problem der NP-Vollständigkeit und sonstige Dinge eine Rolle spielen und ihr deshalb ggfs. weitere Informationen benötigt, um das ganze optimiert zu überdenken, kam ja erst im Laufe des Gesprächs heraus. Das sollte man dabei berücksichtigen.

Ich habe auch mit keinem Wort einen Anspruch auf eine Lösung gestellt. Im Gegenteil: ich hab überhaupt kein Problem damit, wenn ich keine Lösung finde und bin trotzdem allen dankbar, die sich die Mühe machen, gemeinsam mit mir eine Lösung für das Problem zu finden.

Ergänzung (18. November 2015)

[-- Sorry, Doppelpost --]
Davon abgesehen muss man generell eben nicht alle möglichen Kombinationen durchprobieren. Als Beispiel:
Wenn man z.B. bereits genug von den größten Zahlen ausgewählt hat, dann wird man nie auf das passende Ergebnis kommen, egal welche anderen Zahlen man noch dazu nimmt. Das gleiche gilt für Kombinationen die keine der größten Zahlen enthalten.

Äh, was? Bitte um Erklärung.
Was soll das heißen "Wenn man z.B. bereits genug von den größten Zahlen ausgewählt hat, dann wird man nie auf das passende Ergebnis kommen"?
Woher soll das Programm wissen, was "genug" ist, wenn er nicht alle Zahlen durchgeprüft hat?

Wenn ich auf 100 kommen muss und habe 50 und 48 und danach nur noch Zahlen in der Größenordnung "0,1 / 0,2 / 0,3". Was hilft dir das dann? Er muss trotzdem weiter prüfen.

Das gleiche gilt erst Recht, wenn man noch negative Zahlen dabei hat:
Wenn ich auf 100 kommen muss und habe 60 und 60, kann ich nicht einfach aufhören, nur weil ich über dem Zielwert liege.

 

[Tekwar]

Äh, was? Bitte um Erklärung.
Was soll das heißen "Wenn man z.B. bereits genug von den größten Zahlen ausgewählt hat, dann wird man nie auf das passende Ergebnis kommen"?
Woher soll das Programm wissen, was "genug" ist, wenn er nicht alle Zahlen durchgeprüft hat?

Er meint wohl das man bevor man Anfängt die Kombinationen zu prüfen auch einfache Plausibilitätsprüfungen durchführen kann:
Wenn die Summe aller Werte < Zielwert oder wenn alle Einzelwerte > Zielwert sind brauch man erst garnicht anfangen.
Das kann man beliebig erweitern... wenn der kleinste Einzelwert 10 ist kann man zb nie auf einen Zielwert von 111 kommen.

Zum Thema Gewerblich oder nicht:
Ich finde es ist nichts verwerfliches dran wenn man hier Fragen zu einem Problem auf der Arbeit stellt. Solange man keine Fix und Fertige Lösung sucht ist es doch toll wenn man sich über sowas austauschen kann. Ich finde es sogar interessant wenn man mitbekommt was Andere für Probleme zu lösen haben.
Wenn jemand meint das sich jemand durch seine Tips "bereichert" weil er das für die Arbeit nutzt dann soll er halt seine wertvollen Tips für sich behalten....

 

[schmidt206]

Er meint wohl das man bevor man Anfängt die Kombinationen zu prüfen auch einfache Plausibilitätsprüfungen durchführen kann:
Wenn die Summe aller Werte < Zielwert oder wenn alle Einzelwerte > Zielwert sind brauch man erst garnicht anfangen.
Das kann man beliebig erweitern... wenn der kleinste Einzelwert 10 ist kann man zb nie auf einen Zielwert von 111 kommen.

Das ist so nicht richtig.

#1: Zielwert: 10
Einzelwerte: 4,5,6,-8,-1
Summe ist somit 9 und damit < Zielwert.
Trotzdem gibt es die korrekte Lösung 4 & 6.

#3: Zielwert: 111
Einzelwerte: 10, 50, 51
Korrekte Lösung 50 & 51.

Bei dem zweiten Fall stimme ich dir zu. Wenn alle Einzelwerte > Zielwert sind, braucht er gar nicht erst prüfen.

 

[asdfman]

Es gibt noch mehr Trivialfälle. Zum Beispiel wenn jedes Element der Menge größer ist als die Summe aller kleineren Elemente.
Dann gibt es höchstens eine Lösung, die man dann sehr leicht finden kann (Nimm das größte Element, das kleiner oder gleich
der Lösung ist, ziehe seinen Wert von der Lösung ab und wiederhole, bis du bei 0 bist).

Alles Genannte hilft aber für den allgemeinen Fall wenig weiter. Das sind einfache Prüfungen, mit denen man die Menge direkt
ablehnen kann, ohne überhaupt zu versuchen, das Teilsummenproblem zu lösen.

 

[pfd]

Auf dieser Seite gibt es ein paar Implementierungen zur Lösung des Teilsummenproblems. Diese müssten in deinem Fall so optimiert werden, dass nicht 0, sondern eine bestimmte Zahl x die Lösung ist.

Beispielsweise gibt es eine Lösung in C, welche alle Mengen berechnet, welche als Summe 0 ergeben. Da der Code jedoch nicht kommentiert ist, muss dieser selbst analysiert und entsprechend angepasst werden.

 

[Miuwa]

In deiner Beispieldatei sind die 2 größten Werte :

 103.544,03 € 
 129.549,95 €
---------
 233.093,98 €

Alle negativen Werte zusammen ergeben:

-2.647,75 € 
-  935,25 € 
-  174,29 € 
-  153,60 € 
-   52,96 € 
-   15,00 € 
---------
-3.978,85 €

Wenn du also schon die 2 größten Werte ausgewählt hast kannst du niemals auf die geforderten 142.480,93 € kommen. Was bedeutet, durch einfaches Vorsortieren der Zahlen und Berechnen von Teilsummen kannst du schon mal 1/4 der Kombinationen eliminieren (nämlich alle bei denen 103.544,03 € und 129.549,95 € vorkommt).

Oder umgekehrt: Ohne die drei größten Werte kannst du maximal auf 113.293,00 € < 142.480,93 € kommen - also wieder 1/8 weg und es gibt noch ne ganze Reihe an weiteren Spielereien, die man machen kann.

Fazit: Wenn deine Zahlen so ausgesucht sind, dass sie nur eine Lösung ergeben ist die Wahrscheinlichkeit hoch, dass man große Bereiche mit relativ einfachen Möglichkeiten eliminieren kann.

 

[schmidt206]

Es gibt noch mehr Trivialfälle. Zum Beispiel wenn jedes Element der Menge größer ist als die Summe aller kleineren Elemente.

Hä? Wie soll jedes Element größer sein als die Summe der kleineren Elemente (die ja augenscheinlich zu jedes gehören)?

Ergänzung (18. November 2015)

In deiner Beispieldatei sind die 2 größten Werte :

 103.544,03 € 
 129.549,95 €
---------
SUMME:  233.093,98 €

Alle negativen Werte zusammen ergeben:

-2.647,75 € 
-   935,25 € 
-   174,29 € 
-   153,60 € 
-     52,96 € 
-     15,00 € 
---------
-3.978,85 €

Wenn du also schon die 2 größten Werte ausgewählt hast kannst du niemals auf die geforderten 142.480,93 € kommen. Was bedeutet, durch einfaches vorsortieren der Zahlen und berechnen von Teilsummen kannst du schon mal 1/4 der Kombinationen eliminieren (nämlich alle bei denen 103.544,03 € und 129.549,95 € vorkommt).

Oder umgekehrt: Ohne die drei größten Werte kannst du maximal auf 113.293,00 € < 142.480,93 € kommen - also wieder 1/8 weg und es gibt noch ne ganze Reihe an weiteren Spielereien, die man machen kann.

FAzit: Wenn deine Zahlen so ausgesucht sind, dass sie nur eine Lösung ergeben ist die Wahrscheinlichkeit hoch, dass man große Bereiche mit relativ einfachen Möglichkeiten eliminieren kann.

Ah, alles klar, jetzt hab ich verstanden, was du meinst.
Das ist ohne Zweifel richtig!

 

[asdfman]

Hä? Wie soll jedes Element größer sein als die Summe der kleineren Elemente (die ja augenscheinlich zu jedes gehören)?

Zum Beispiel so: { 16 8 4 32 2 1 }
Sortiert: { 1 2 4 8 16 32 }

32 > 1 + 2 + 4 + 8 + 16
16 > 1 + 2 + 4 + 8
8 > 1 + 2 + 4
4 > 1 + 2
2 > 1

Wenn man 11 haben will:
Größtes Element, kleiner oder gleich 11: 8 (1. Element der Lösungsmenge). 11 - 8 = 3
Größtes Element, kleiner oder gleich 3: 2 (2. Element der Lösungsmenge). 3 - 2 = 1
Größtes Element, kleiner oder gleich 1: 1 (3. Element der Lösungsmenge). 1 - 1 = 0

Lösung: { 8 2 1 }

 

[schmidt206]

Zum Beispiel so: { 16 8 4 32 2 1 }
Sortiert: { 1 2 4 8 16 32 }

32 > 1 + 2 + 4 + 8 + 16
16 > 1 + 2 + 4 + 8
8 > 1 + 2 + 4
4 > 1 + 2
2 > 1

Wenn man 11 haben will:
Größtes Element, kleiner oder gleich 11: 8 (1. Element der Lösungsmenge). 11 - 8 = 3
Größtes Element, kleiner oder gleich 3: 2 (2. Element der Lösungsmenge). 3 - 2 = 1
Größtes Element, kleiner oder gleich 1: 1 (3. Element der Lösungsmenge). 1 - 1 = 0

Lösung: { 8 2 1 }

Alles klar, dann war dein Satz nur schwierig formuliert.
Verständlich!

 

[Traxx555]

Und genau so wird das was. Einige Restriktionen bzw. Modellerweiterung wurde ja schon genannt.
Und dann baust du das ganze wie o.g. in ein Matlab oder Cplex Modell und los! Einmal das Grundmodell aufgesetzt und laufen lassen, dann fällts leichter weitere Optimierungen rein zu kriegen. Das bekommst schon hin, so schlimm schaut das ja nicht aus um eine brauchbare Lösung zu erhalten. Vereinfachen kannst du es i.d.R. immer damit du eine sehr geringe Laufzeit erhältst, je nach Anspruch der Optimalität.

 

[andy_m4]

negative Werte

Das gleiche gilt erst Recht, wenn man noch negative Zahlen dabei hat:
Wenn ich auf 100 kommen muss und habe 60 und 60, kann ich nicht einfach aufhören, nur weil ich über dem Zielwert liege.

Doch kann man.
Um es sich einfacher zu machen, mapped man die Zahlen einfach auf positive Werte in dem man zu allen Zahlen und den Zielwert einfach den Absolutwert der kleinsten Zahl die vorkommt addiert. Dann braucht man in der Lösung nicht mehr darauf zu achten, dass nachfolgend noch negative Zahlen kommen können die die bisher errechnete Zwischensumme wieder nach unten ziehen.

Man kann nach dem Mapping einfach die Zahlen aus der Liste streichen, die über dem Zielwert liegen.

So kann man mit einfachsten Mitteln schon die Menge der Zahlen, die man überhaupt in den eigentlichen Algorithmus schickt, ggf. erheblich reduzieren.

Gruß
Andy

 

[S.Kara]

AW: negative Werte

zu allen Zahlen und den Zielwert einfach den Absolutwert der kleinsten Zahl die vorkommt addiert.

Das funktioniert mathematisch nicht.
Du müsstest zum Zielwert n*abs(min) addieren, wobei n die Anzahl der Werte ist, aus die der Zielwert am Ende besteht.

 

[Miuwa]

Dann nenn' mir doch gerne mal eine Lösung. Ich bin gespannt.
Ich bezweifle sehr stark, dass du "mehrere Millionen Lösungen" dafür bekommst. Ich bezweifle sogar, dass du mir überhaupt 2 Lösungen posten kannst.

Ich hab mir mal nur jede 2^20. Lösung ausgeben lassen:

1048576:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 65462 + 63069 + 59850 + 57358 + 55710 + 52360 + 51884 + 50410 + 48609 + 47599 + 44950 + 42431 + 42245 + 41650 + 40110 + 39000 + 37095 + 37009 + 36729 + 33640 + 31086 + 30176 + 29600 + 29560 + 21215 + 20900 + 20111 + 19900 + 19828 + 17500 + 17429 + 16929 + 16645 + 15360 + 8507 + 2202 + 1678 + 1652 + 1500 + 1449 + 1198 + 1197 + 424   	=14248093
2097152:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 65462 + 63069 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 44950 + 42431 + 42245 + 41650 + 40110 + 39000 + 37095 + 37009 + 36729 + 33640 + 30176 + 29600 + 29560 + 23445 + 21215 + 20111 + 19900 + 19829 + 17500 + 17429 + 17295 + 16645 + 15360 + 15355 + 13203 + 8507 + 5296 + 1678 + 1652 + 1449 + 1198 + 1197  	 	=14248093
3145728:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 65462 + 63069 + 59850 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 44950 + 42431 + 42245 + 41650 + 40110 + 39000 + 37095 + 36729 + 33640 + 31086 + 30176 + 29600 + 29560 + 27152 + 23445 + 21215 + 20900 + 20111 + 19900 + 19829 + 17429 + 17295 + 16929 + 15355 + 8507 + 5296 + 2202 + 1678 + 1652 + 1500  	  	  	=14248093
4194304:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 67143 + 67100 + 65482 + 65481 + 65462 + 63069 + 59850 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 42431 + 42245 + 41650 + 40110 + 39000 + 37095 + 37009 + 36729 + 30176 + 29600 + 29560 + 27152 + 23445 + 21215 + 20900 + 20111 + 19900 + 19829 + 19828 + 18445 + 17500 + 17429 + 8507 + 5296 + 1678 + 1500 + 1198 + 1197 + 424  	  	 	 	=14248093
5242880:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 65482 + 65481 + 65462 + 63069 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 44950 + 42431 + 42245 + 41650 + 40110 + 39000 + 37009 + 36729 + 31086 + 30176 + 29600 + 29560 + 27152 + 23445 + 20900 + 19900 + 19829 + 19828 + 18445 + 17500 + 17429 + 17295 + 16929 + 15360 + 13203 + 5296 + 2202 + 1678 + 1652 + 1449 + 1197 + 424  	  	=14248093
6291456:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65481 + 65462 + 63069 + 59850 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 42245 + 41650 + 40110 + 39000 + 37095 + 37009 + 36729 + 33640 + 31086 + 30176 + 29600 + 29560 + 27152 + 21215 + 20900 + 20111 + 19829 + 19828 + 18445 + 17500 + 16929 + 15355 + 13203 + 1678 + 1500 + 1449 + 1197  	  	 	  	 	=14248093
7340032:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 63069 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 44950 + 42245 + 41650 + 40110 + 39000 + 37095 + 37009 + 33640 + 31086 + 30176 + 29600 + 29560 + 27152 + 23445 + 21215 + 20900 + 19829 + 19828 + 18445 + 17500 + 17429 + 17295 + 16645 + 15360 + 15355 + 13203 + 1652 + 1449 + 1198  	  	 	 	=14248093
8388608:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 65462 + 59850 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 44950 + 42431 + 42245 + 41650 + 40110 + 39000 + 37009 + 33640 + 31086 + 30176 + 29600 + 29560 + 27152 + 23445 + 20900 + 20111 + 19900 + 19829 + 19828 + 17500 + 17295 + 16645 + 15360 + 13203 + 8507 + 5296 + 1500 + 1449  	  	 	 	 	=14248093
9437184:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 65462 + 63069 + 57358 + 55710 + 52360 + 51884 + 50410 + 48671 + 48609 + 47599 + 44950 + 42431 + 42245 + 41650 + 40110 + 37095 + 37009 + 36729 + 31086 + 30176 + 29600 + 29560 + 27152 + 23445 + 21215 + 20900 + 20111 + 19900 + 18445 + 17500 + 16929 + 5296 + 1652 + 1500 + 1449 + 424  	  	 	 	 	 	=14248093
10485760:	6095180 + 1245000 + 998500 + 777070 + 657594 + 300000 + 264775 + 259479 + 257754 + 253238 + 250138 + 202062 + 108552 + 99000 + 96000 + 93552 + 93525 + 89250 + 88417 + 86513 + 83900 + 83895 + 83776 + 82600 + 80976 + 72450 + 67143 + 67100 + 65482 + 65481 + 65462 + 63069 + 59850 + 57358 + 52360 + 50410 + 48671 + 48609 + 47599 + 44950 + 42431 + 41650 + 40110 + 39000 + 37095 + 37009 + 36729 + 33640 + 31086 + 30176 + 29600 + 29560 + 27152 + 21215 + 20111 + 19900 + 19829 + 19828 + 17500 + 16645 + 15360 + 15355 + 13203 + 5296 + 1449 + 424  	  	 	 	 	 	=14248093

Das war das Ergebnis von einer Minute Rechenzeit.

 

[maxator]

10485760 Lösungen in einer Minute? Da würde mich doch glatt mal die Programmiersprache und die Hardware interessieren.

 

[schmidt206]

Krass, würde mich auch mal interessieren!

 

[Miuwa]

C++ auf nem ivy i5.
Ich glaube aber, die hohe Anzahl an gefundenen Lösungen deutet mehr darauf hin, dass es insgesamt so viele Lösungen gibt und nicht, dass das Programm so effizient ist.

Ergänzung (20. November 2015)

So, hier der Code - der Übersichtlichkeit halber hab ich die negativen Zahlen rausgenommen, aber die waren bei den gefundenen Lösungen eh nicht dabei.:

#include <array>
#include <iostream>

constexpr size_t ValueCnt = 87;
constexpr std::array<int, ValueCnt>  values   {	12954995, 10354403, /*... Sortierte Werte ...*/ 1197 ,424 };
constexpr std::array<int, ValueCnt>  partSums {	40733878, 27778883, /*... Partialsummen  ... */ 1621 ,424 };

std::array<bool, ValueCnt> selected{};
size_t solutionCnt = 0;

constexpr int TARGET = 14'248'093;

template<size_t I>
void run(int sum) {	
	if (sum == TARGET) {
		solutionCnt++;
		//print solution
		return;
	}

	if ((TARGET < sum) || (sum + partSums[I] < TARGET)) return;

	run<I + 1>(sum);
	selected[I] = true;
	run<I + 1>(sum + values[I]);
	selected[I] = false;
}

template<>
void run<ValueCnt>(int sum) {
	if (sum == TARGET) {
		solutionCnt++;
		//print solution		
	}
}

int main() {
	run<0>(0);
	std::cout << solutionCnt << std::endl;	
}