Tool zum Matchen von Zahlen, um auf Zielwert zu kommen

[schmidt206]

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.

Hat jemand eine Idee?

Gruß,
schmidt206

 

[blöderidiot]

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]

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]

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]

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

 

[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.

 

[schmidt206]

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.

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.

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.

 

[asdfman]

Subset Sum Problem. NP-vollständig. Viel Spaß dabei.

https://en.m.wikipedia.org/wiki/Subset_sum_problem

 

[Cool Master]

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]

Subset Sum Problem. NP-vollständig. Viel Spaß dabei.

https://en.m.wikipedia.org/wiki/Subset_sum_problem

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]

Ob jetzt 0 oder ein anderer Zielwert rauskommen soll, ist egal.
Zitat ein Satz weiter:

An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s?

 

[schmidt206]

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]

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]

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

 

[VikingGe]

Es geht um €-Werte

€-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?

 

[Cool Master]

€-Werte sind ganzzahlig.

199,99 € wo ist das ein int? Das ist ein float oder ein double

 

[simpsonsfan]

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.

 

[crvn075]

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).

 

[Cool Master]

Ja ok an Cent habe ich dem Moment nicht gedacht muss ich ehrlich zugeben

 

[schmidt206]

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?