Tool zum Matchen von Zahlen, um auf Zielwert zu kommen

schmidt206

Commander
Dabei seit
Dez. 2007
Beiträge
2.059
Servus,

Folgendes Szenario:
Ich habe n Einzelwerte, sowohl positiv als auch negativ.
Ich möchte auf einen vorgegebenen Zielwert y kommen.
Ich benötige ein Tool, dass mir aus diesen n Einzelwerten die Kombination(en) raussucht, mit welchen ich auf Zielwert y komme.

Wir hatten eine selbst programmierte Lösung in der Firma, die aber zich Jahre alt ist, relativ langsam arbeitet - und für die der Quellcode leider vor einigen Jahren verloren gegangen ist. :rolleyes:

Hat jemand eine Idee?

Gruß,
schmidt206
 

blöderidiot

Captain
Dabei seit
Juni 2004
Beiträge
3.348
Ich habe n Einzelwerte, sowohl positiv als auch negativ.
Ich möchte auf einen vorgegebenen Zielwert y kommen.
Ich benötige ein Tool, dass mir aus diesen n Einzelwerten die Kombination(en) raussucht, mit welchen ich auf Zielwert y komme.
Das ist unklar ausgedrückt. Kannst du das genauer beschreiben und ein konkretes Beispiel liefern? Was sind "Kombinationen"?
 

Cool Master

Fleet Admiral
Dabei seit
Dez. 2005
Beiträge
28.574
Wenn ich es richtig Verstanden habe ist es so:

Ziel: 250

Werte: 5, 10, 9000, 400, 200, 50, 1, 5

Es müssen also die Werte 200 und 50 genommen werden.

Habe ich das richtig verstanden?
 

Hommie

Ensign
Dabei seit
Nov. 2006
Beiträge
144
Ich vermute mal sowas ist gemeint?

n = 3
y = 9

Kombinationen: n *3 , n+6

Edit:
ok, dass von Cool Master macht mehr Sinn^^
 

max_1234

Captain
Dabei seit
Feb. 2012
Beiträge
3.682
Nö, weil wesentliche Infos wie z.B. die maximale Anzahl von Zahlen zum "Kombinieren" nicht genannt wurde.
Außerdem handelt es sich hier um eine (wenn auch ungewollt?) gewerbliche Anfrage. Wenn ihr keine Rechnungen ausstellen könnt, dann lasst es lieber sein ;)

mfg,
Max
 
V

VikingGe

Gast
Zwei Fragen:
a) Welche "Kombinationen" sind erlaubt? Additionen? Irgendwas anderes?
b) Dürfen Einzelwerte mehrfach verwendet werden?
c) Gibt es irgendwelche Voraussetzungen, die das Ergebnis erfüllen muss? (möglichst wenige Zahlen, ...) - oder brauchst du alle möglichen Kombinationen (was keinen Sinn ergibt, wenn Frage b) mit 'ja' beantwortet wird)
d) Nur ganzzahlige Werte oder Gleitkommawerte?

Eine einfache Brute Force-Version zu dem Thema kann man sich wohl recht schnell zusammencoden - spannend wird es erst, wenn das ganze optimiert werden soll.
 

schmidt206

Commander
Ersteller dieses Themas
Dabei seit
Dez. 2007
Beiträge
2.059
Zitat von Cool Master:
Wenn ich es richtig Verstanden habe ist es so:

Ziel: 250

Werte: 5, 10, 9000, 400, 200, 50, 1, 5

Es müssen also die Werte 200 und 50 genommen werden.

Habe ich das richtig verstanden?
Genau so. Es geht nur um Addition von genannten Zahlen.

Zitat von max_1234:
Nö, weil wesentliche Infos wie z.B. die maximale Anzahl von Zahlen zum "Kombinieren" nicht genannt wurde.
Außerdem handelt es sich hier um eine (wenn auch ungewollt?) gewerbliche Anfrage. Wenn ihr keine Rechnungen ausstellen könnt, dann lasst es lieber sein

mfg,
Max
Maximale Anzahl ist n, also im schlechtesten Fall eine Kombination aus allen Einzelwerten.
Ich möchte das nicht gewerblich nutzen. Ich hatte nur vorher ein Tool, was jemand aus meiner Firma programmiert hatte, für welches wir aber den Quellcode nicht haben. Ich suche quasi nach einer Freeware-Alternative.

Zitat von VikingGe:
Zwei Fragen:
a) Welche "Kombinationen" sind erlaubt? Additionen? Irgendwas anderes?
b) Dürfen Einzelwerte mehrfach verwendet werden?
c) Gibt es irgendwelche Voraussetzungen, die das Ergebnis erfüllen muss? (möglichst wenige Zahlen, ...) - oder brauchst du alle möglichen Kombinationen (was keinen Sinn ergibt, wenn Frage b) mit 'ja' beantwortet wird)
d) Nur ganzzahlige Werte oder Gleitkommawerte?

Eine einfache Brute Force-Version zu dem Thema kann man sich wohl recht schnell zusammencoden - spannend wird es erst, wenn das ganze optimiert werden soll.
Deine zwei Fragen sind 4 :-p
a) nur Additionen
b) nein
c) nein, brauche alle Kombinationen
d) beides. Es geht um €-Werte

Das bisherige Tool läuft nach einer Art BruteForce-Methode. Bei meinem Beispiel mit 273 Einzelwerten und dafür maximal 2^273-1 Kombinationsmöglichkeiten braucht das Tool ca. 1,9 Mrd. Jahre - so viel Zeit hab ich nicht.
 

Cool Master

Fleet Admiral
Dabei seit
Dez. 2005
Beiträge
28.574
Außerdem handelt es sich hier um eine (wenn auch ungewollt?) gewerbliche Anfrage. Wenn ihr keine Rechnungen ausstellen könnt, dann lasst es lieber sein ;)
Auch wenn es OT is:

Jeder kann und darf eine Rechnung ausstellen. Er muss den Umsatz nur dem Finanzamt melden und damit eben die MwSt abführen und möglicherweise Steuern zahlen wenn es über dem Freibetrag ist.

Dazu kommt, auch wenn es schon gesagt wurde, sucht er nicht nach einem Auftragnehmer sondern etwas fertiges.
 

schmidt206

Commander
Ersteller dieses Themas
Dabei seit
Dez. 2007
Beiträge
2.059
Danke für den Link; leider versteh ich den Zusammenhang zu meinem Problem nicht, weil ich es so interpretiere, dass die Summierung von nicht-leeren Subsets zu einer Summe 0 das Problem darstellen.
In meinem Fall wird der Zielwert vorgegeben, der niemals 0 sein kann.

Kannst du mir das in wenigen Worten erläutern?
 

simpsonsfan

Commander
Dabei seit
Feb. 2008
Beiträge
2.786

schmidt206

Commander
Ersteller dieses Themas
Dabei seit
Dez. 2007
Beiträge
2.059
Ob jetzt 0 oder ein anderer Zielwert rauskommen soll, ist egal.
Zitat ein Satz weiter:
Danke, aber ich verstehe das equivalent problem daran nicht.
Ich sehe eine Umformulierung meiner Anforderung, aber das eigentlich Problem nicht.
Geht das hierbei nur um Optimierungspotential? Weil funktionieren tut's ja augenscheinlich mit unserer Methode - es dauert halt nur ewig.
 

blöderidiot

Captain
Dabei seit
Juni 2004
Beiträge
3.348
brauche alle Kombinationen
Es geht um €-Werte
Hmmm, na ja, das ist schon einen "stattliches" Problem und nur lösbar, wenn es Vereinfachungen gibt. Dazu:

In welchem Bereich (Minimum, Maximum) liegen die 273 "Funktionswerte" Y?
Wie groß kann minimal und maximal so eine gesuchte reale Summe S sein?

Oder besser: poste doch mal deine Liste Y[0..272] und ein paar gewünschte S.
 

asdfman

Commander
Dabei seit
März 2008
Beiträge
2.315
Danke, aber ich verstehe das equivalent problem daran nicht.
Ich sehe eine Umformulierung meiner Anforderung, aber das eigentlich Problem nicht.
Geht das hierbei nur um Optimierungspotential? Weil funktionieren tut's ja augenscheinlich mit unserer Methode - es dauert halt nur ewig.
Wenn man so will, ist es eine Frage der Optimierbarkeit. Leider ist aber für NP-vollständige Probleme keine "schnelle" Lösung bekannt und es wird auch vermutlich nie eine geben.
Wenn du eine Methode findest, die dein Problem im allgemeinen Fall schnell berechnen kann, wäre das eine sehr große Leistung, die du unbedingt veröffentlichen solltest.

https://de.wikipedia.org/wiki/NP-Vollständigkeit
 
V

VikingGe

Gast
€-Werte sind ganzzahlig. Aber das macht das Problem zumindest schonmal lösbar, bei echten Gleitkommazahlen könntest du im Allgemeinen nicht einmal eine Summe genau berechnen.

Geht das hierbei nur um Optimierungspotential? Weil funktionieren tut's ja augenscheinlich mit unserer Methode - es dauert halt nur ewig.
In dem Wikipedia-Artikel ist ein Algorithmus mit dynamischer Programmierung gegeben, mit dem man zumindest einige der Teilmenge(n), die die gewünschte Summe liefern, rekonstruieren kann. Ob du damit alle Teilmengen findest - weiß ich nicht, ohne mich damit intensiver auseinanderzusetzen.


Mal so aus Interesse, wofür wird das ganze eigentlich benötigt?
 
Zuletzt bearbeitet:

Cool Master

Fleet Admiral
Dabei seit
Dez. 2005
Beiträge
28.574

simpsonsfan

Commander
Dabei seit
Feb. 2008
Beiträge
2.786
Das sind exakt 19 999ct. Und das sollte man auch so behandeln.

Und das Problem an der ganzen Sache ist, dass es keinen effizienten Algorithmus gibt, um das ganze zu berechnen.
Brute-Force würde funktionieren, vorausgesetzt, man hat Zeit, Rechen- und Speicherkapazität.
Und "equivalent" wäre "äquivalent" auf deutsch, das Problem ist deshalb das gleiche, weil du, wenn du in deine Menge einfach mal noch ein Element mit Wert -s aufnimmst ansonsten die gleichen Teilmengen suchst, deren Summe 0 ergibt.
 
Zuletzt bearbeitet: (typo)

crvn075

Lt. Junior Grade
Dabei seit
Juli 2015
Beiträge
429
Nur weil ein Problem NP-vollständig ist und sich im Sinne der theoretischen Informatik vermutlich nicht "effizient" lösen lässt, heißt das nicht, dass man nicht trotzdem in annehmbarer Zeit eine Lösung bekommt, die entweder appoximativ (bsp: genetische Algorithmen für das TSP) oder mit Einschränkungen gar genau ist. Da es sich beim Teilsummenproblem nur ein "schwaches" NP-vollständiges Problem handelt, gibt es dafür auch Möglichkeiten, es in pseudopolynomialer Zeit zu lösen. Ein Ansatz ist der bereits erwähnte Weg, dynamische Programmierung zu nutzen und das Endergebnis aus Teilsummen aufzubauen, die aber jeweils nur einmal berechnet und dann gespeichert werden.

Ich bin mir momentan aber noch im unklaren darüber, ob das Verlangen nach allen möglichen Summen nicht ein KO-Kriterium darstellt. Wichtig für den Ansatz wären aber sowieso erstmal die von blöderidiot gestellte Fragen nach den 272 Werten und der Gesamtsumme. Wenn die Zahlen weit auseinanderliegen, dann funktioniert der Ansatz schlecht bis gar nicht.

199,99 € wo ist das ein int? Das ist ein float oder ein double ;)
Wenn dir dein Geld egal ist, dann bildest du es als float oder double ab :)
Auch wenn unglücklich formuliert ist doch klar, dass er auf eine Abbildung ohne Kommas hinaus wollte (199,99 => 19999).
 
Zuletzt bearbeitet:

schmidt206

Commander
Ersteller dieses Themas
Dabei seit
Dez. 2007
Beiträge
2.059
Danke für eure Antworten.
Kann ich die 273 Einzelwerte hier in einer Liste posten, oder sprengt das den Thread? Oder soll ich die als txt linken?
 
Top