Некоторая компания устраивает вечеринку для определенного количества сотрудников, и чтобы устроить хорошую вечеринку, компании приходится покупать разные сорта пива. У каждого сотрудника есть свое любимое пиво. Задача состоит в том, чтобы определить, сколько разных сортов пива необходимо купить компании, чтобы не оскорблять сотрудников.
Исходные данные:
2 2
YN NY
Выходные данные:
2
(первая строка содержит 2 числа, первая - количество сотрудников, а вторая - количество доступных напитков. Во второй строке показаны символы Y-да (означает сотрудника). как этот сорт пива), N-нет (означает, что сотруднику не нравится этот сорт пива))
Исходные данные:
6 3
YNN YNY YNY NYY NYY NYN
Выходные данные:
2
(наиболее оптимальным будет купить пиво 1 и 3 сортов)
Ограничения
0 < employees < 50
0 < beers < 50
Мои мысли и предположения:
мы можем представить эту проблему в виде двудольного графа, чтобы слева были сотрудники, а справа - сортировкипива. Отношение между ними - предпочтение сотрудника. Как мы можем найти этот минимум?
Какой алгоритм может решить эту проблему? Есть ли другие подходы?
Буду признателен за любую помощь!