Array SubSum Solver
Seite 1 von 1
Array SubSum Solver
Der Array basierte iterative Solver bringt es bei n=8 die minimale Lösung
solution: [1, 23, 35, 38, 41, 45, 47, 49]
5 of 449196254 are solutions
2270390ms
sind ~37 Minuten.
Zugegeben angefangen mit einem uper bound von 50.
Die erste Lösung die er findet ist gleich die optimale
und es gibt mit 49 noch weiter 4 Lösungen
solution: [1, 23, 35, 38, 41, 45, 47, 49]
5 of 449196254 are solutions
2270390ms
sind ~37 Minuten.
Zugegeben angefangen mit einem uper bound von 50.
Die erste Lösung die er findet ist gleich die optimale
und es gibt mit 49 noch weiter 4 Lösungen
johannes- Anzahl der Beiträge : 4
Punkte : 6
Anmeldedatum : 17.03.10
mögliches Performance Tuning
Mir ist folgendes eingefallen:
Unsere Gewichtsberechnung nimmt ja ein Set und den Counter.
Dann berechnet er das Gewicht für die Zahlen mit den gesetzten 1-bits.
Eigentlich könnten wir ja mit einem Counter Wert gleich zwei Subset-Gewichte berechnen.
Die 0er ergeben das komplementäre Set das wir später nochmal betrachten.
Dadurch könnten wir den counter nur mehr bis zur hälfte laufen lassen
und trotzdem alle Gewichte berechenen.
Unsere Gewichtsberechnung nimmt ja ein Set und den Counter.
Dann berechnet er das Gewicht für die Zahlen mit den gesetzten 1-bits.
Eigentlich könnten wir ja mit einem Counter Wert gleich zwei Subset-Gewichte berechnen.
Die 0er ergeben das komplementäre Set das wir später nochmal betrachten.
Dadurch könnten wir den counter nur mehr bis zur hälfte laufen lassen
und trotzdem alle Gewichte berechenen.
johannes- Anzahl der Beiträge : 4
Punkte : 6
Anmeldedatum : 17.03.10
Seite 1 von 1
Befugnisse in diesem Forum
Sie können in diesem Forum nicht antworten
|
|