Przypisywanie grup

Question

Mam problem gdzie mam przypisywać zmienne do zbiorów. Każdy zestaw ma limit zmiennych, które można do niego przypisać, a każdą zmienną można przypisać do jakiegoś podzbioru wszystkich zestawów.

Przykład:

• amogą być w zestawach AlubB
• b mogą być w zestawach B
• cmogą być w zestawach AlubB
• d mogą być w zestawach A

Zatem możemy mieć A: a, d; B: b, club A: c, d; B: a,b(kolejność zmiennych w zbiorze nie ma znaczenia) /

Oczywiście będą chwile, kiedy nie będzie możliwe przypisanie wszystkich zmiennych, chwile, kiedy będziemy mieli wiele opcji i czasy, gdy będzie tylko jedna opcja.

Wydaje mi się, że istnieje prosta wersja tego problemu, ale nie mogę jej wskazać. Wszelkie wskazówki będą mile widziane.

Answer 1

Wydajne rozwiązanie przy maksymalnym przepływie. Przygotuj sieć przepływu z jednostkową wydajnością łukową od źródła do każdej zmiennej, jednostkową wydajnością łuku z każdej zmiennej do każdego zestawu, do którego może należeć, oraz łukiem z każdego zestawu do pochłaniacza o pojemności równej pojemności zestawu . Na przykład,

ARCS

tail head capacity
------------------
s    a    1
s    b    1
s    c    1
s    d    1
a    A    1
a    B    1
b    B    1
c    A    1
c    B    1
d    A    1
A    t    2
B    t    2

Użyj swojego ulubionego algorytmu maksymalnego przepływu, który generuje integralny przepływ i wyodrębnij przypisanie, zgodnie z którym zmienna do ustawienia łuków ma przepływ.

Answer 2

Ten problem jest NP-zupełny, co oznacza, że ​​nie ma na to rozwiązania wielomianowego. W takim przypadku musiałbyś użyć cofania.

Spójrz na te linki:

https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/ https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/