Erstmal in eigener Sache: Wenn es bei den naechsten Contests um Geschwindigkeit wie hier geht, die Zeitmessung ohne Floating Point zu machen ( zu mindestens wenn man wie hier so oft misst ). Eine Optimierung mittels MMX / SSE/ SSE2 im Integerbereich ist dann nicht zum scheitern verurteilt. Aktuell hilft es mir aber nichts, bin noch bei reinem C/C++ :-).
@spacegaier: Naja, du faengst an, erstmal den Dummy-Algorithmus zu implementieren (exakter Loeser) und schaust dann weiter. Mein zweiter war dann Meet-in-the-middle. Dann schaust du wie sich der Algorithmus verhaelt, wann und wo er langsam ist. Dann kannst du weiter schauen: Approximationsalgorithmen etc. ... und schaust, wann und wo sie langsam sind. Und dann kannst du sie optimieren. Ich glaube ich habe den schnellsten Meet-in-the-middle Algorithmus, den man mit "C" hinkriegen kann zumindestens bis Laenge 40 oder so), leider ist er immer noch nicht gut genug. Der andere Weg ist, sich zu fragen, warum greedy so gut ist, wann und wo das passiert und dort optimieren, mein eigener greedy lag bei 1.33 Vergleich. Dann kannst du weggehen vom allgemeinem Ansatz und der Aufgabenstellung angepasst, dich nur auf Probleme der Groesse 50 oder weniger beschraenken. Und vieles mehr ...... Btw. ich mag die Aufgabenstellung.
Da es ein NP-vollstaendiges Problem ist, solltest du nicht zu viel erwarten, ein Faktor 2 ist da schon gigantisch. Btw. sortieren muss ich auch mal, nutze sogar die STL dafuer :-).