Array SubSum Solver

Vorheriges Thema anzeigen Nächstes Thema anzeigen Nach unten

Array SubSum Solver

Beitrag  johannes am Fr Mai 21, 2010 9:51 am

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

johannes

Anzahl der Beiträge : 4
Punkte : 6
Anmeldedatum : 17.03.10

Benutzerprofil anzeigen

Nach oben Nach unten

mögliches Performance Tuning

Beitrag  johannes am Sa Mai 22, 2010 1:20 pm

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.

johannes

Anzahl der Beiträge : 4
Punkte : 6
Anmeldedatum : 17.03.10

Benutzerprofil anzeigen

Nach oben Nach unten

Vorheriges Thema anzeigen Nächstes Thema anzeigen Nach oben


 
Befugnisse in diesem Forum
Sie können in diesem Forum nicht antworten