[Algorytmy] Wybór osób na spotkanie

[Julia321]

Mam pewne zadanie:

Jan organizuje szkolne spotkanie. Dany uczeń nie zjawi się na spotkanie, jeżeli będzie na nim inny uczeń, którego nie lubi. Wiadomo, że każdy lubi Jana. Zadaniem Jana jest wysłać zaproszenia tak wybranym osobom, by na spotkaniu zjawiło się jak najwięcej osób.

Dane wejściowe:

Kod: Zaznacz cały

n - liczna uczniów do zaproszenia
[n][n] - macierz n x n, z wypełnionymi polami (1 - lubi ucznia, 0 nie lubi)

Wyjście:

Kod: Zaznacz cały

k - maksymalna liczba uczniów, którą Jan może zaprosić

np.
WEJŚCIE:

Kod: Zaznacz cały

5
1 1 0 1 0
1 1 0 1 1
0 0 1 0 0
1 1 0 1 0
0 1 0 0 1

WYJSCIE:

Kod: Zaznacz cały

3

Czy ktoś ma pomysł jak najbardziej optymalnie to zrobić?

[jutrvy]

Czy zakładamy, że człowiek \(\displaystyle{ x}\) lubi człowieka \(\displaystyle{ y}\) wtedy i tylko wtedy, gdy człowiek \(\displaystyle{ y}\) lubi człowieka \(\displaystyle{ x}\), czyli po ludzku, że relacja \(\displaystyle{ x}\) lubi \(\displaystyle{ y}\) jest zwrotna?

[Afish]

Czy ktoś ma pomysł jak najbardziej optymalnie to zrobić?

Nie ma „najbardziej optymalnie”, albo coś jest optymalne, albo nie jest.

Co do problemu. Osoby lubiące się nic nie wnoszą, więc zajmujemy się tylko tymi nielubiącymi się. Tworzymy graf, w którym krawędź między A i B jest wtedy i tylko wtedy, gdy A nie lubi B lub B nie lubi A.

Następnie w takim grafie chcemy znaleźć maximum independent set (nie mylić z maximal independent set):

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_sets