Cool Master
Fleet Admiral
- Registriert
- Dez. 2005
- Beiträge
- 37.413
Glaube ein .txt Anhang wäre besser wegen der Übersicht.
Folge dem Video um zu sehen, wie unsere Website als Web-App auf dem Startbildschirm installiert werden kann.
Anmerkung: Diese Funktion ist in einigen Browsern möglicherweise nicht verfügbar.
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.
Wer findet den Fehler? Klar, matchen von Eurowerten als Privathobby. Also eigentlich doch gewerblich.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.
Ernsthaft? Weil das hochzahlige €-Werte sind?Mextli schrieb:Wer findet den Fehler? Klar, matchen von Eurowerten als Privathobby. Also eigentlich doch gewerblich.
Nicht ganz. 273^273 wäre jede Kombination. Ich untersuche aber nach a+b+c nicht erneut b+a+c.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.
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;
}
};
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
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.Die Reihenfolge ist schließlich egal.
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.weniger wenn man bedenkt, dass viele Zahlen mehrfach vorkommen
Auch noch so ein Punkt, wo man sich fragt, ob der TE überhaupt nach dem richtigen Problem fragt.Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen
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.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?
Wie darf ich das verstehen?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.
Lösungen oder Kombinationsmöglichkeiten? Ich tippe doch mal auf letzteres?Miuwa schrieb:Also ich bekomme selbst ohne die negativen Einträge zigmillionen Lösungen
Dann erzähl uns doch mal, was du erreichen willst.Eine würde vermutlich auch reichen, aber wenn es genau die letzte Möglichkeit ist, ist mir damit ja nicht geholfen.
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.Mehrfach vorkommende Zahlen dürfen gerne eliminiert werden.
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: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.
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: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.
Nein, ich meinte schon Lösungen - allerdings unter der Annahme, dass Zahlen, die mehrfach vorkommen auch mehrfach verwendet werden können.schmidt206 schrieb:Lösungen oder Kombinationsmöglichkeiten? Ich tippe doch mal auf letzteres?
Cool Master schrieb:199,99 € wo ist das ein int? Das ist ein float oder ein double
Mextli schrieb:Wer findet den Fehler? Klar, matchen von Eurowerten als Privathobby. Also eigentlich doch gewerblich.
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.
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.mambokurt schrieb:Und wen schert das? Ist es verboten hier um Hilfe zu fragen wenn man ein Problem auf Arbeit hat?
Das sind die 273 beispielhaften Einzelwerte, die in bestimmter Kombination einen Betrag von 142.480,93 ergeben sollen.
Ich habe es nun zwei Mal erläutert. Aber ich sage es gerne auch noch ein drittes Mal.Mextli schrieb:Nö, aber wer was beruflich nutzt soll auch für diese Leistung bezahlen.
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.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.
Danke, das werd ich mal ausprobieren. Vielleicht bringt mich das ja weiter.Traxx555 schrieb:Hab jetzt nicht den ganzen Thread verfolgt, allerdings mit Matlab hast du es schon probiert?
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.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.
Dann nenn' mir doch gerne mal eine Lösung. Ich bin gespannt.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?