Tool zum Matchen von Zahlen, um auf Zielwert zu kommen

Glaube ein .txt Anhang wäre besser wegen der Übersicht.
 
Ja, besser als .txt oder im [spoiler]...[/spoiler]-Tag.
 
Anbei die werte.txt.
Das sind die 273 beispielhaften Einzelwerte, die in bestimmter Kombination einen Betrag von 142.480,93 ergeben sollen.
 

Anhänge

  • werte.txt
    1,9 KB · Aufrufe: 180
schmidt206 schrieb:
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.
schmidt206 schrieb:
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.
Wer findet den Fehler? Klar, matchen von Eurowerten als Privathobby. Also eigentlich doch gewerblich. :p
 
Also wenn es da keinen mathematischen Trick gibt, sind das 273^273 mögliche Kombinationen und das ist einfach zu viel.

Wenn es sein muss, würde ich zunächst den Mittelwert bilden und der Reihe nach alle Werte raussuchen, die dem Mittelwert am nächsten sind. Sowie der nächste Wert den Zielwert überschreiten würde, müssen nach und nach die Mittelwerte mit den nächstgrößeren ausgetauscht werden usw.
Im worst case ist die Läufzeit zwar noch schlechter, im avg könnte man so aber evtl. etwas besser liegen.

Lade dein Programm doch mal hoch, dann könnte man dem Teil mal auf die Finger gucken.
 
Mextli schrieb:
Wer findet den Fehler? Klar, matchen von Eurowerten als Privathobby. Also eigentlich doch gewerblich. :p
Ernsthaft? Weil das hochzahlige €-Werte sind? :freak:
Das sind randomisierte Werte aus Excel, die ich als Beispiel genommen habe, um das (in der Firma programmierte) Tool auf seine Möglichkeiten zu testen, weil man mir das freundlicherweise für private Zwecke zur Verfügung gestellt.
Was ich damit später anstelle, ist doch auch vollkommen egal. Ich suche ja nach einer Fertiglösung und möchte es nicht extra programmieren lassen.

S.Kara schrieb:
Also wenn es da keinen mathematischen Trick gibt, sind das 273^273 mögliche Kombinationen und das ist einfach zu viel.
Lade dein Programm doch mal hoch, dann könnte man dem Teil mal auf die Finger gucken.
Nicht ganz. 273^273 wäre jede Kombination. Ich untersuche aber nach a+b+c nicht erneut b+a+c.
Das schließt auch meine bisherige Lösung bereits aus. Es bleibt trotzdem noch einer sehr sehr große Zahl :p
Hochladen geht leider nicht. Ist wie gesagt eine Lösung von der Firma.
 
Ich glaube nicht, dass es für so etwas, was sich nunmal wirklich nicht effizient lösen lässt, irgendeine Lösung gibt, die besser ist als die, die ihr ohnehin schon benutzt.

Das Problem an der Sache ist einfach, dass du nach allen Lösungen suchst. Würdest du mit einer Vorlieb nehmen, wäre das kein Problem - ich habe hier mal eine Implementierung gebaut, die mit deinem Datensatz innerhalb weniger Sekunden eine Lösung findet und dabei alle zur Verfügung stehenden CPU-Kerne nutzt:

Code:
class SubsetSumState {
  
public:
  
  SubsetSumState(const Array<int32>& numbers)
  : SubsetSumState(Array<int32>(numbers)) { }
  
  SubsetSumState(Array<int32>&& numbers)
  : _numbers(std::move(numbers)) {
    
    this->_numbers.walkIndexed([this] (size_t i, int32 n) {
      // Compute positive and negative sums
      this->_posSum += n > 0 ? n : 0;
      this->_negSum += n < 0 ? n : 0;
      // Obviously, the number itself is the sum of a subset
      // of the number array. Store the smallest index.
      if (!this->_arrayNumbers.get(n))
        this->_arrayNumbers.insert(n, i);
    });
    
    // Create lookup array
    this->_rowIndices = Array<LookupEntry>(this->_posSum - this->_negSum + 1);
    
  }
  
  
  List<int32> solve(int32 target) {
    
    // Find one number that has to be part of the result.
    const size_t rowIndex = this->getRowIndexParallel(target, this->_numbers.size());
    
    if (rowIndex == INVALID_INDEX)
      return List<int32>();
    
    // In case the number we found is equal to
    // the target value, the set containing only
    // this number is a valid solution.
    const int32 number = this->_numbers[rowIndex];
    
    if (number == target)
      return List<int32>({ number });
    
    // Otherwise, we need to recursively check
    // the remaining numbers.
    List<int32> result = this->solve(target - number);
    result.append(number);
    
    // Copy elision doesn't work here
    return std::move(result);
    
  }
  
  
private:
  
  // Invalid row index that is used to indicate that the
  // problem cannot be solved for a given target number.
  constexpr static size_t INVALID_INDEX = Limits::Max<size_t>;
  
  // Lookup table entry
  struct alignas(16) LookupEntry {
    LookupEntry() { }
    LookupEntry(size_t i, size_t l)
    : index(i), limit(l) { }
    Atomic<size_t> index = { INVALID_INDEX };
    Atomic<size_t> limit = { 0 };
  };
  
  // Source array
  const Array<int32> _numbers;
  
  // Map that stores the smallest index of a number that
  // is part of a solution for each possible target.
  Array<LookupEntry> _rowIndices;
  
  // Map that stores the index for each array number.
  ReferenceGuard<Maps::HashTable<int32, size_t>> _arrayNumbers;
  
  int32 _posSum = 0;
  int32 _negSum = 0;
  
  
  size_t getRowIndex(int32 target, size_t indexLimit) {
    
    // If the index limit is 0, exit early to avoid
    // problems during later steps.
    if (indexLimit == 0 || target < this->_negSum || target > this->_posSum)
      return INVALID_INDEX;
    
    // Lookup array index
    const size_t lookupIndex = target - this->_negSum;
    
    // Look up the target in the row index table.
    // If it is successful, we've found our result.
//     const LookupEntry lookupEntry = this->_rowIndices[lookupIndex];
    LookupEntry lookupEntry;
    
    asm volatile (
      "movdqa (%0), %%xmm0;"
      "movdqa %%xmm0, (%1);"
      :
      : "r" (&this->_rowIndices[lookupIndex]), "r" (&lookupEntry)
      : "xmm0", "memory");
    
    if (lookupEntry.index < indexLimit)
      return lookupEntry.index;
    
    // If the first known solution requires a higher index limit
    // or if there is no solution at all, we won't find one here.
    if (lookupEntry.limit >= indexLimit)
      return INVALID_INDEX;
    
    // Check if the number itself is included in the array
    // and if its index is below the current index limit.
    size_t numberIndex = INVALID_INDEX;
    
    if (this->_arrayNumbers.get(target, numberIndex) && numberIndex < indexLimit)
      return numberIndex;
    
    // If not, check if we can find a solution using
    // one of the numbers from the number array.
    size_t recursiveIndex = INVALID_INDEX;
    
    this->_numbers.walkRangeIndexedUntil(lookupEntry.limit + 1, indexLimit - lookupEntry.limit - 1,
      [this, target, &recursiveIndex] (size_t i, int32 n) -> bool {
        
        const size_t subIndex = this->getRowIndex(target - n, i);
        
        // If the new index for the previous number
        // target is valid, we've found a solution.
        if (subIndex != INVALID_INDEX) {
          recursiveIndex = i;
          return true;
        } return false;
          
      });
    
    // If the solution is valid, write it to the index
    // table for future lookups and return it
    asm volatile (
      // Read old lookup entry
      "movq 0(%3), %%rax;"
      "movq 8(%3), %%rdx;"
      // New lookup entry
      "movq %0, %%rbx;"
      "movq %1, %%rcx;"
      
      "1:"
      "lock cmpxchg16b (%2);"
      "jz 2f;"
      
      // In case the limit we want to write is greater
      // than the limit in memory, override it.
      "cmp %%rdx, %%rcx;"
      "jg 1b;"
      
      "2:"
      : 
      : "r" (recursiveIndex), "r" (indexLimit), "r" (&this->_rowIndices[lookupIndex]), "r" (&lookupEntry)
      : "rax", "rbx", "rcx", "rdx", "memory"
    );
//     this->_rowIndices[lookupIndex] = LookupEntry(recursiveIndex, indexLimit);
    return recursiveIndex;
    
  }
  
  
  size_t getRowIndexParallel(int32 target, size_t indexLimit) {
    
    if (indexLimit == 0 || target < this->_negSum || target > this->_posSum)
      return INVALID_INDEX;
    
    // Check if the number itself is included in the array
    // and if its index is below the current index limit.
    size_t numberIndex = INVALID_INDEX;
    
    if (this->_arrayNumbers.get(target, numberIndex) && numberIndex < indexLimit)
      return numberIndex;
    
    // Walk over all numbers and process them in parallel.
    Atomic<size_t> result = { INVALID_INDEX };
    
    WinSystem::Module::jobManagerSync()->execute(
      [this, &result, target] (volatile Jobs::JobGroup* jobGroup) {
        
        volatile Jobs::JobQueue* jobQueue = jobGroup->createJobQueue();
        
        this->_numbers.walkIndexed(
          [this, &jobGroup, &jobQueue, &result, target]
          (const size_t i, const int32 n) {
            jobGroup->createJob(jobQueue,
              [this, &result, target, i, n] {
                
                if (result != INVALID_INDEX)
                  return;
                
                const size_t subIndex = this->getRowIndex(target - n, i);
                
                // If the new index for the previous number
                // target is valid, we've found a solution.
                if (subIndex != INVALID_INDEX)
                  result.compareAndSwap(INVALID_INDEX, i);
                
              })->start();
          });
        
      });
    
    return result;
    
  }
  
};

Lösung (in Cent):
Code:
250138  5296  -15360  88417  40110  37009  19828  1197  19828  1197  19829  33640  1198  57358  1500  20900  23445  96000  1678  36729  17429  264775  257754  13203  12954995
= 14248093

Mit dem Code wird zwar so direkt niemand was anfangen können, aber das Prinzip sollte klar sein.

Auf alle Lösungen erweitern lässt sich das allerdings nicht, da müsste man schon alle Permutationen (273! - etwa 10^548) der ursprünglichen Menge ausprobieren. :freak:
 
Zuletzt bearbeitet:
Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen - wenn ich den Computer noch ne Weile laufen lassen würde wärens wahrscheinlich noch ein paar Größenordnungen mehr. Kannst du mal erklären, was du mit dem Ergebnis willst und warum es ALLE möglichen Kombinationen sein müssen?

@VikingGe:
Ich hab deinen Algorithmus jetzt nicht analysiert, aber kannst du kurz erklären, wie du auf diese Zahlen kommst? Es gibt schließlich "nur" maximal 2^273 Kombinationen - weniger wenn man bedenkt, dass viele Zahlen mehrfach vorkommen. Die Reihenfolge ist schließlich egal.
 
Zuletzt bearbeitet:
Die Reihenfolge ist schließlich egal.
Bei dem DP-Algorithmus nicht, das ist das Problem. Aber du hast natürlich recht, an sich ist der Aufwand deutlich geringer - selbst wenn man die Brute Force-Methode wählt.

Trotzdem liegt 2^273 ein paar Größenordnungen jenseits dessen, was man bis zur Explosion der Sonne so berechnen kann. :freak:

weniger wenn man bedenkt, dass viele Zahlen mehrfach vorkommen
Ist jetzt die Frage, ob wir von einer mathematischen Menge reden oder ob mehrfach vorkommende Zahlen auch mehrfach in der Lösung vorkommen dürfen. Ich bin jetzt von letzterem ausgegangen, macht letztlich aber kaum einen Unterschied.

Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen
Auch noch so ein Punkt, wo man sich fragt, ob der TE überhaupt nach dem richtigen Problem fragt.
 
Zuletzt bearbeitet:
Miuwa schrieb:
Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen - wenn ich den Computer noch ne Weile laufen lassen würde wärens wahrscheinlich noch ein paar Größenordnungen mehr. Kannst du mal erklären, was du mit dem Ergebnis willst und warum es ALLE möglichen Kombinationen sein müssen?
Eine würde vermutlich auch reichen, aber wenn es genau die letzte Möglichkeit ist, ist mir damit ja nicht geholfen. Vermutlich wird es bei den Zahlen auch in den meisten Fällen nur genau eine Möglichkeit geben.

VikingGe schrieb:
Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen
Auch noch so ein Punkt, wo man sich fragt, ob der TE überhaupt nach dem richtigen Problem fragt.
Wie darf ich das verstehen?
Mehrfach vorkommende Zahlen dürfen gerne eliminiert werden. Das kann man aber natürlich auch vorher schon manuell durchführen, um die Anzahl der Möglichkeiten zu senken. Aber es können eben auch 150 einzigartige Werte sein.

Miuwa schrieb:
Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen
Lösungen oder Kombinationsmöglichkeiten? Ich tippe doch mal auf letzteres?
 
Eine würde vermutlich auch reichen, aber wenn es genau die letzte Möglichkeit ist, ist mir damit ja nicht geholfen.
Dann erzähl uns doch mal, was du erreichen willst.
Und was meinst du mit "letzte Möglichkeit"? Es gibt eigentlich nur Lösungen und Nicht-Lösungen, darauf jetzt eine Ordnung zu definieren, halte ich nicht für sinnvoll.

Mehrfach vorkommende Zahlen dürfen gerne eliminiert werden.
Das verändert aber auch die Lösungsmenge. In der von meinem Code ermittelten Lösung wird z.B. der Wert 1197 mehrfach verwendet, weil er auch mehrfach in der Liste vorkommt.
 
Zuletzt bearbeitet:
schmidt206 schrieb:
Eine würde vermutlich auch reichen, aber wenn es genau die letzte Möglichkeit ist, ist mir damit ja nicht geholfen. Vermutlich wird es bei den Zahlen auch in den meisten Fällen nur genau eine Möglichkeit geben.
Und das schließt du woraus? Wenn du uns verraten würdest, was denn das eigentliche Ziel ist und woher die Zahlen kommen, könnte man dir vielleicht auch sinnvolle Tipps geben. Und es macht durchaus einen Unterschied ob man möglichst effizent nach EINER Lösung sucht und danach fertig ist oder ob man möglichst effizient ALLE Möglcihkeiten prüfen muss.

schmidt206 schrieb:
Mehrfach vorkommende Zahlen dürfen gerne eliminiert werden. Das kann man aber natürlich auch vorher schon manuell durchführen, um die Anzahl der Möglichkeiten zu senken.
Wieso gibts du uns dann eine Datei, in dem es bei 273 Einträgen gerade mal 83 Verschiedene Zahlen gibt? Alle möglichen Kombinationen aus 273 Zahlen zu untersuchen ist praktisch unmöglich. EINE Kombination aus 83 Zahlen zu finden, die das Kriterium erfüllt liegt - je nach Situation - durchaus im Bereich des Machbaren.

schmidt206 schrieb:
Lösungen oder Kombinationsmöglichkeiten? Ich tippe doch mal auf letzteres?
Nein, ich meinte schon Lösungen - allerdings unter der Annahme, dass Zahlen, die mehrfach vorkommen auch mehrfach verwendet werden können.
 
Cool Master schrieb:
199,99 € wo ist das ein int? Das ist ein float oder ein double ;)

Ganz fieser Fehler, wenn du jemals mit Geldbeträgen rechnen solltest mach bloß von Anfang an Cent draus, sonst musst du alle Nase lang auf 2 Nachkommastellen runden :D
Ergänzung ()

Mextli schrieb:
Wer findet den Fehler? Klar, matchen von Eurowerten als Privathobby. Also eigentlich doch gewerblich. :p

Und wen schert das? Ist es verboten hier um Hilfe zu fragen wenn man ein Problem auf Arbeit hat? :freak:
Ergänzung ()

schmidt206 schrieb:
Eine würde vermutlich auch reichen, aber wenn es genau die letzte Möglichkeit ist, ist mir damit ja nicht geholfen. Vermutlich wird es bei den Zahlen auch in den meisten Fällen nur genau eine Möglichkeit geben.

..oder gar keine.

Meine 2 Cent: Wenn du ein Problem hast, erkläre das Problem nicht abstrahiert. Mal unabhängig von deinen Werten und deiner Summe die du versuchst zusammenzuaddieren - wozu machst du das? Ich frage das nicht, weil ich dir auf die Nerven gehen will. Ich habe den ganzen Tag mit Kunden zu tun, die mpt aufwändigen Ideen zu mir kommen. Letztendlich ist es dann aber immer das selbe: "Wozu wollen Sie das machen? Ach Sie wollen XYZ? Na da machen Sie doch einfach ZYX! Ja klar funktioniert das auch! Nichts zu danken, tschüss.".

Sprich wozu addierst du denn da die Untersummen zusammen?
 
mambokurt schrieb:
Und wen schert das? Ist es verboten hier um Hilfe zu fragen wenn man ein Problem auf Arbeit hat? :freak:
Nö, aber wer was beruflich nutzt soll auch für diese Leistung bezahlen. Aber die Diskussion darüber würde hier zu weit führen. Helf Du ruhig weiter.
 
Das sind die 273 beispielhaften Einzelwerte, die in bestimmter Kombination einen Betrag von 142.480,93 ergeben sollen.

Definier doch erstmal welche Eigenschaften diese "bestimmte" Kombination haben soll. Möglichst wenig Einzelwerte, möglichst viele, möglichst große(...)

Sonst schnapp dir einen beliebige Umsetzung des "Teilsummenproblem" und lass es bis zu einer gewissen Anzahl an Lösungen laufen. Aber das wurde hier ja schon zu genüge beschrieben.
 
Ich verstehe ja immer noch nicht, was hiermit überhaupt bezweckt werden soll. Was nützt mir ein Tool, dass mir mehrere Millionen Lösungen rausspuckt? Geht man danach per Hand durch und sucht sich nach weiteren Kriterien eine Lösung raus? Warum muss es genau der Zielwert sein? Fragen über Fragen.
Meine Vermutung ist hier einfach ganz stark, dass die falsche Problemstellung angegangen wird.

So lange, bis hier mehr Infos kommen, klinke ich mich mal wieder aus. Es gab einfach schon genügend Threads, wo man dem TE alles aus der Nase ziehen wollte und ihm seitenlang versucht zu erklären, dass es nicht immer nötig ist den Versuch zu unternehmen ein praktisch unlösbares Problem (weil riesige Eingabe und begrenzte Rechenzeit) zu lösen.
 
Hab jetzt nicht den ganzen Thread verfolgt, allerdings mit Matlab hast du es schon probiert?
Ich löse meine Optimierungsprobleme mit ILOG Cplex auf nem größeren Server, kommt natürlich drauf an ob du eine Optimalitätslücke erlaubst, reale Zahlen (leichter) nur Ganzzahlen etc. Am Modell selbst, welches du vorgibts lässt sich natürlich auch einiges beschränken und anpassen.
 
Mextli schrieb:
Nö, aber wer was beruflich nutzt soll auch für diese Leistung bezahlen.
Ich habe es nun zwei Mal erläutert. Aber ich sage es gerne auch noch ein drittes Mal.
Selbst wenn ich beruflich nutzen würde: ich suche nach eine fertigen Lösung und möchte nichts programmieren lassen.
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?
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.

daemon777 schrieb:
Ich verstehe ja immer noch nicht, was hiermit überhaupt bezweckt werden soll. Was nützt mir ein Tool, dass mir mehrere Millionen Lösungen rausspuckt? Geht man danach per Hand durch und sucht sich nach weiteren Kriterien eine Lösung raus? Warum muss es genau der Zielwert sein? Fragen über Fragen.
Meine Vermutung ist hier einfach ganz stark, dass die falsche Problemstellung angegangen wird.

So lange, bis hier mehr Infos kommen, klinke ich mich mal wieder aus. Es gab einfach schon genügend Threads, wo man dem TE alles aus der Nase ziehen wollte und ihm seitenlang versucht zu erklären, dass es nicht immer nötig ist den Versuch zu unternehmen ein praktisch unlösbares Problem (weil riesige Eingabe und begrenzte Rechenzeit) zu lösen.
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.
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.

Traxx555 schrieb:
Hab jetzt nicht den ganzen Thread verfolgt, allerdings mit Matlab hast du es schon probiert?
Danke, das werd ich mal ausprobieren. Vielleicht bringt mich das ja weiter.
 
Zuletzt bearbeitet:
schmidt206 schrieb:
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.
Hab ich auch ausprobiert und selbst dann hab ich nach ein paar Stunden Rechenzeit auf einem Kern mehrere millionen Lösungen zusammen gehabt. Ich will nicht aussschließen, dass mein Code fehlerhaft ist, aber ich glaube es nicht. Wenn ich Zeit habe werde ich ihn mal raussuchen und posten.
Nochmal: woher kommt die Annahme, dass es nur eine oder keine Lösung gibt?
 
Miuwa schrieb:
Hab ich auch ausprobiert und selbst dann hab ich nach ein paar Stunden Rechenzeit auf einem Kern mehrere millionen Lösungen zusammen gehabt. Ich will nicht aussschließen, dass mein Code fehlerhaft ist, aber ich glaube es nicht. Wenn ich Zeit habe werde ich ihn mal raussuchen und posten.
Nochmal: woher kommt die Annahme, dass es nur eine oder keine Lösung gibt?
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.

Weil ich weiß, um welche Werte es in meinem Beispiel geht.
Und nochmal: es ist völlig egal, ob es keine, eine oder mehrere Lösungen gibt. Er muss trotzdem schlechtestenfalls alle Kombinationen prüfen.
Zur Vereinfachung könnte man auch sagen, dass die erste passende Lösung reicht und das Programm da stoppt. Wie gesagt: bei den Zahlen, wofür dieses Tool notwendig wäre, wird es nur eine oder keine Lösung geben.
 
Zurück
Oben