Dana jest grupa \(\displaystyle{ n}\) osób. Niektóre znają się nawzajem ,relacja symetryczna. Tę grupę osób należy jak najtaniej zakwaterować w hotelu , gdzie są jednoosobowe pokoje rodzajów: z tv bez WC ( x zł ), z WC bez tv( x zł ) , bez WC i bez tv ( y zł ) . Każda osoba lub jej bezpośredni znajomy musi posiadać dostęp do obu odogodnień.
Mam problem z powyższym zadaniem. Zadanie mam wykonać tak aby wyszła jak najniższa złożoność obliczeniowa jednak nie jestem pewien który algorytm odpowiada temu zadaniu . Według moich rozważań wychodzi graf nieskierowany który łączy ze sobą cechy szufladkowania i najtańszego przepływu.
Z drugiej strony wpadłem na dość prosty sposób polegający na następujących krokach:
- przydzielenie wszystkim pokoju z tv
- po jednym znajomemu pokoj z WC , jesli w parze jest WC lub tv to pomijam
- reszcie osób pokój za 30 zł ,jeśli w parze brakuje tv lub WC to przydzielić to jednej osobie z pary
Bardzo liczę na rady jaki algorytm byłby najodpowiedniejszy do tego zadania
