Na stołach \(\displaystyle{ T={ t _{1},..., t _{n} }}\) stoi dokładnie \(\displaystyle{ a( t _{i} )}\) szklanek. Do dyspozycji mamy kelnerów \(\displaystyle{ K={k _{1},...,k _{n}}}\)którzy sprzątają stoły, jednak kelner \(\displaystyle{ k _{j}}\) może zabrać maksymalnie \(\displaystyle{ b( k _{j} )}\) szklanek na raz. Na dodatek : każdy stół może zostać posprżatany przez dokładnie jednego kelnera, albo wcale, każdy kelner może posprzątać maksymalnie jesen stół.
Podaj algorytm który przyporządkuje kelnerów do stołów tak, że liczba posprzątanych stołów bedzie największa z możliwych.
Proszę o pomoc
[Algorytmy] Szklanki i kelnerzy
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
[Algorytmy] Szklanki i kelnerzy
Robimy graf dwudzielny. W jednym zbiorze wierzchołkami są stoły, a w drugim kelnerzy. Łączymy kelnera krawędziami z tymi stołami, na których jest nie więcej szklanek niż może wysprzątać ten kelner. W takim grafie znajdujemy maksymalne skojarzenie. Każda krawędź oznacza przyporządkowanie kelnera do stołu (który jest w stanie obsłużyć) - do każdego stołu jest przypisany co najwyżej jeden kelner i każdy kelner do co najwyżej jednego stołu. Wielkość tego skojarzenia to maksymalna liczba możliwych posprzątanych stołów.
Maksymalne skojarzenie w grafie dwudzielnym można wyznaczyć np. algorytmem Hopcrofta-Karpa w czasie \(\displaystyle{ O(\left| E\right| \sqrt{\left| V\right| } )}\).
-- 29 października 2016, 14:34 --
To skojarzenie można wyznaczyć szybciej, bo ten graf ma szczególne własności.
Posortujmy stoły według rosnącego \(\displaystyle{ a}\). Teraz każdy kelner jest w stanie obsłużyć spójny odcinek stołów od najmniejszego \(\displaystyle{ a}\) do takiego które nie przekracza jego \(\displaystyle{ b}\). Posortujmy dodatkowo kelnerów po \(\displaystyle{ b}\) rosnąco. Teraz każdy kolejny kelner jest w stanie obsłużyć coraz dłuższy odcinek stołów.
Zrobimy algorytm zachłanny, który każdemu kelnerowi, w kolejności rosnącego \(\displaystyle{ b}\), przyporządkowuje jeszcze nieprzyporządkowany stół o jak najmniejszym \(\displaystyle{ a}\) (które jest nie większe niż \(\displaystyle{ b}\) tego kelnera).
Ten algorytm jest poprawny, bo jeżeli w maks. skojarzeniu jest "dziura" w wykorzystanych stołach to możemy przesunąć wybory kelnerów do stołów o mniejszych \(\displaystyle{ a}\). Ponadto jeżeli kelnerzy \(\displaystyle{ i}\) oraz \(\displaystyle{ j}\) tacy, że \(\displaystyle{ b_{i} \le b_{j}}\) obsługują stoły: \(\displaystyle{ i}\) obsługuje stół \(\displaystyle{ k}\), a \(\displaystyle{ j}\) stół \(\displaystyle{ l}\) takie, że \(\displaystyle{ a _{k} > a _{l}}\) to można zamienić ich stoły i rozwiązanie nie będzie gorsze.
Czas działania \(\displaystyle{ O\left( \left| V\right| \cdot log\left| V\right| \right)}\) (bo trzeba posortować).
Maksymalne skojarzenie w grafie dwudzielnym można wyznaczyć np. algorytmem Hopcrofta-Karpa w czasie \(\displaystyle{ O(\left| E\right| \sqrt{\left| V\right| } )}\).
-- 29 października 2016, 14:34 --
To skojarzenie można wyznaczyć szybciej, bo ten graf ma szczególne własności.
Posortujmy stoły według rosnącego \(\displaystyle{ a}\). Teraz każdy kelner jest w stanie obsłużyć spójny odcinek stołów od najmniejszego \(\displaystyle{ a}\) do takiego które nie przekracza jego \(\displaystyle{ b}\). Posortujmy dodatkowo kelnerów po \(\displaystyle{ b}\) rosnąco. Teraz każdy kolejny kelner jest w stanie obsłużyć coraz dłuższy odcinek stołów.
Zrobimy algorytm zachłanny, który każdemu kelnerowi, w kolejności rosnącego \(\displaystyle{ b}\), przyporządkowuje jeszcze nieprzyporządkowany stół o jak najmniejszym \(\displaystyle{ a}\) (które jest nie większe niż \(\displaystyle{ b}\) tego kelnera).
Ten algorytm jest poprawny, bo jeżeli w maks. skojarzeniu jest "dziura" w wykorzystanych stołach to możemy przesunąć wybory kelnerów do stołów o mniejszych \(\displaystyle{ a}\). Ponadto jeżeli kelnerzy \(\displaystyle{ i}\) oraz \(\displaystyle{ j}\) tacy, że \(\displaystyle{ b_{i} \le b_{j}}\) obsługują stoły: \(\displaystyle{ i}\) obsługuje stół \(\displaystyle{ k}\), a \(\displaystyle{ j}\) stół \(\displaystyle{ l}\) takie, że \(\displaystyle{ a _{k} > a _{l}}\) to można zamienić ich stoły i rozwiązanie nie będzie gorsze.
Czas działania \(\displaystyle{ O\left( \left| V\right| \cdot log\left| V\right| \right)}\) (bo trzeba posortować).