Ja za 2^n*n^2 mam 8pkt

Jak Psyho zarzucił kodem, to miałem nadzieję, że jakaś dobra heura tam będzie, która rozwaliła wszystkie testy w 0.01s, a tam standardowy dynamik :(

Potwierdzam i testy Konrada i Krzyśka.

Cześć. To dorzucam jeszcze jeden:
in : http://speedy.sh/gVehV/par-test.in
out: http://speedy.sh/jdXWd/par-test.out

czy ktoś może powiedzieć na ile wchodziło 2^n*n^2?

Limity były takie, że nawet dobrze przycięty backtrack wszedł na 10 z maksymalnym czasem:

10e OK 10.56s/15.00s

http://pastebin.com/yiUxnhkA

Hiperkostka ma n2^(n-1) krawędzi, rozwiązanie zadania bez przejrzenia każdej po razie wydaje mi się bardzo mało prawdopodobne. Na szczęście limity były takie, że spokojnie wchodziło i moje 3h żyłowania zdały się na nic :P (pakowanie numeru plecaka w pierwsze 5 bitów, a następnie wykorzystanej pojemności do następnych 27 bitów unsigned intów było zabawne :P).

Wolne to to jest moje O(3^n * m) :P

Ja napisałem to O(n*2^n) i moim zdaniem to jest wolne. Nie da się jakoś szybciej ? A może podpowiecie jakieś skuteczne optymalizacje?

Cześć,
To może jeszcze ja się podzielę kilkoma testami.
http://speedy.sh/KhCzh/test-rand.tar.xz

A mój na test 32 TAK
8 2 4 6 7 5 1 3 9 10
(:

Dynamik po podzbiorach, dla każdego wyliczasz ile musisz wziąć plecków i ile miejsca zostaje w ostatnim. I wychodzi O(n * 2^n).

Jakie jest rozwiązanie do PAK ? Coś mądrzejszego niż n splotów, które dawało O(n^2 * 2^n) ?

Potwierdzam oba zestawy (nie1 i nie2 z ręcznie poprawionymi wysokościami).
Czas maksymalny ~2,3s.