Zadanie Studenci
Oto inne ciekawe zadanie, które można rozwiązać, korzystając z masek bitowych:
Dla danej liczby , rozpatrujemy studentów i zadań. Każdy student lubi pewne wybrane zadania. Twoim zadaniem jest obliczyć, na ile sposobów można przyporządkować dokładnie po jednym zadaniu do każdego studenta, tak aby każdy otrzymał inne zadanie i każdy lubił zadanie, które otrzymał. Studentów będzie co najwyżej 20.
Pierwsza rzecz, która jest istotna, to fakt, że studentów jest niewielu. Dopuszcza to rozwiązania działające w czasie wykładniczym. Zauważamy też, że w zadaniu chcemy policzyć, ile jest pełnych skojarzeń zbiorów studentów i zadań.
Ten problem, podobnie jak TSP, jest trudny. Zliczanie ilości pełnych skojarzeń to zadanie bardzo pracochłonne i nie znane są algorytmy, działające w czasie wielomianowym, które rozwiązywałyby ten problem. Jeśli chcesz dowiedzieć się więcej na ten temat, polecam artykuł na Wikipedii, na temat Permanentu - pojęcia matematycznego, związanego z naszym problemem.
Szukajmy wobec tego dobrego rozwiązania w wykładniczym czasie.
Możemy podejść do problemu w ten sposób - gdyby zliczać skojarzenia stopniowo, dla coraz większych podzbiorów studentów, nie trzeba by pamiętać, któremu studentowi przydzielono które zadanie, a jedynie którzy studenci i które zadania są już „zajęte”. Jeśli przyjmiemy, że będziemy rozpatrywać studentów po kolei, znajdując ilość skojarzeń najpierw dla studenta nr 1, potem dla studentów 1 i 2, i tak dalej, to będziemy musieli wiedzieć dwie rzeczy:
- którego studenta obecnie rozpatrujemy
- które zadania są już przydzielone (nie interesuje nas, które do kogo)
Pierwsze wymaganie załatwia nam zwykła pętla, drugie zaspokaja metoda masek bitowych - zapamiętujemy, który podzbiór zadań został już przydzielony. Będziemy obliczać dynamicznie wartości dla kolejnych stanów. Oznaczmy:
- zbiór zadań.
- zbiór studentów.
- ilość skojarzeń pierwszych studentów z podzbiorem zbioru .
= 1, jeśli studentowi x można przydzielić zadanie z, 0 w przeciwnym razie.
Dla uproszczenia notacji będziemy też przyjmować, że oznaczenie zbioru to zarazem oznaczenie jego maski bitowej, w kontekście, w którym jest wymagana (np. dla zbioru , wartość odnosi się w drugim parametrze tablicy do maski bitowej zbioru ).
Nasz algorytm będzie wyglądał tak, że przeglądać będziemy kolejnych studentów i dla
k-tego w kolejności studenta, przeglądniemy te podzbiory zbioru zadań, których moc wynosi
(chcemy mieć dokładne skojarzenie). Takie podzbiory mamy zapamiętane, dzieki metodzie generowania masek bitowych wraz z ilością ich zapalonych bitów. Teraz dla ustalonego i podzbioru , potencjalnie każde z zadań z (oznaczmy takie zadanie ) mogło zostać przydzielone studentowi o numerze , o ile . Musimy więc przeiterować po elementach (znamy metodę sprawdzania, które bity są zapalone), dla każdego zapalonego bitu na pewnej pozycji sprawdzić, czy student o numerze może otrzymać to zadanie, i do wartości dodać wartość , jeśli to możliwe. Dzięki temu, uzyskamy sumę wszystkich możliwości przydziału :
Rozwiązaniem jest wartość , czyli ilość wszystkich możliwych skojarzeń pomiędzy pełnymi zbiorami studentów i zadań.
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany.
Zaloguj się lub
załóż konto.