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

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

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?

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

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).

http://pastebin.com/yiUxnhkA

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

10e OK 10.56s/15.00s

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

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 :(

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

Dało się na 9 (tak mój pierwszy submit punktował).

Ale potem poprawiłem i u mnie chodziło ~30-40% szybciej, ale u nich 1.1 do 3 razy wolniej... i ostatecznie dostałem tylko 8 pkt. Może jakieś kwestie innego rozmiaru cache'a albo coś, a może sam źle pomierzyłem se czasy... no cóż trudno konkursować i pracować jednocześnie (szczególnie jak i tak do finału się nie zakwalifikuje...).

W każdym razie za O(N**2 * 2**N) dało się 9 pkt uzyskać.
W pierwszym submicie tylko 10-ty test mi uwaliło i to tylko na 3 podtestach [10b, 10e, 10f], być może dałoby się to trochę jeszcze wyżyłować i zaliczyć na 10 (choć 10a mi rozwiązywało też bardzo na styk: 14.17s/15s, i 9a: 4.42s/5s).

Update:

rozwiązanie O(N**2 * 2**N) za 9 pkt, oficjalne czasy:
0..9 OK
10a OK 14.17s/15.00s
10b TLE 15.12s/15.00s
10c OK 5.42s/15.00s
10d OK 3.10s/15.00s
10e TLE 15.14s/15.00s
10f TLE 15.11s/15.00s

Ile chodzi u mnie [i5-2520M CPU @ 2.50GHz, 3MB cache]:
Test 10a: 6.315s
Test 10b: 8.542s
Test 10c: 2.450s
Test 10d: 1.415s
Test 10e: 7.929s
Test 10f: 7.094s

Jak widać jakoś 2.25 razy szybciej.
Wniosek: 8.5s u mnie to pewnie ~19.1s czasu oficjalnego.

Nie wiem czy aż 25% czasu dałoby się jeszcze z tego wyżyłować...
Być może? Trzeba by pewnie trochę pokombinować...

Jedno z moich n^2*2^n przeszło na 10 i to wcale nie na styk :)
Z tego co widziałem to bardzo dużo mu dawało przesortowanie przedmiotów rosnąco.

słabe limity, u mnie 10f 2.94/15s
Szkoda, że tak mała różnica punktowa między O(n^2 2^n) a wzorcówką :/

Rozumiem, że nie chce się nikomu opisywać szczegółowiej rozwiązanie, ale rzućcie kodami rozwiązań na 8-10;)
U mnie kiepski backtracking z limitem iteracji (zwraca najlepsze co znalazł) prostą heurystyką od góry (pakuj pierwsze co pasuje) i dolnym oszacowaniem "L2" stąd http://www.or.deis.unibo.it/kp/Chapter8.pdf Pewnie jakby zaimplementować całość z tej pracy działałoby lepiej (tylko być może, bo tam plecaki są równej wielkości) a tak 4 punkty (mogło być 5 jakbym limitów nie podbił:)


Edit: Jest rozwiązanie oficjalne, dynamiczne, takie jak w podanym przez Przemysława kodzie.
https://www.youtube.com/watch?v=-b1WqgSr2vk

Random też dawał niemało punktów, bo aż 6 maksymalny czas 0.24s/15.00s.

Wydawało mi się, że już rzuciłem kodem. Tam jest raptem kilkanaście linii do "analizowania", a opis "Dynamik po podzbiorach, dla każdego wyliczasz ile musisz wziąć plecków i ile miejsca zostaje w ostatnim. I wychodzi O(n * 2^n). " praktycznie wyczerpuje temat.

Edit: No właśnie ;)

Wystarczające jak się wie jak zrobić:) Musiałem się wczoraj trochę pogapić na ten kod aby go rozszyfrować i zrozumieć;)
Było parę innych metod. Np chciałbym zobaczyć, jak wygląda dobry backtrack dla tego zadania - Piotrowi taka metoda weszła 10/10. Obejrzenie heurystyk też może być ciekawe.

http://pastebin.com/7S5PByW4

W skrócie:
Dla ustalonej liczby plecaków próbuję pakować plecaki od najmniejszego. W jednym ruchu pakuję od razu cały plecak pewnym podzbiorem przedmiotów, przy czym:
- do danego plecaka pakuję tylko maksymalne ze względu na zawieranie podzbiory, które się w nim mieszczą
- jeżeli dla plecaka istnieje para podzbiorów tej samej mocy, które różnią się dokładnie jednym elementem to nie sprawdzam tego o mniejszej wadze
- podzbiory sprawdzam w kolejności malejącej ze względu na pary (liczba przedmiotów, łączna waga)
- obcinam jak wiem że w pozostałych plecakach zabraknie mi miejsca na resztę przedmiotów.

Czasami na max testach przeszukiwanie trwało zbyt długo dla liczby plecaków za małej o 1, wtedy po przekroczeniu limitu iteracji zakładałem, że się nie da. Porównując 2 ostatnie zgłoszenia, tylko na teście 10e miałem taką sytuację.

> Jedno z moich n^2*2^n przeszło na 10 i to wcale nie na styk :)
> Z tego co widziałem to bardzo dużo mu dawało przesortowanie przedmiotów rosnąco.

Michał (albo ktoś inny) rzucilibyście takim kodem o n*n*2**n złożoności, a 10 pkt? Ciekaw jestem coście tam porobili ;-)

https://gist.github.com/embe/38c1a0a69f2a16d4cf9e

O(n 2^n):
http://pastebin.com/wSK9j7wS

Heura na 9/10 (błąd na 8f):
http://pastebin.com/SPVpT3j3

Generowanie pełnych stanów (używając BFS-a) opisujących każdy plecak przy zakładaniu kolejnych m. Jeśli ilość stanów przekroczy to co byłem w stanie zmieścić w pamięci to stwierdzam, że się da dla aktualnego m.

Na wszystkich testach nr 9 czas 0.00s/5.00s