Алгоритм минимальной группировки

Question

У меня есть набор значений, каждое значение имеет возможную группу.Значение может повторяться, но в другой группе.

Какой будет оптимальный алгоритм для получения минимального количества групп

Пример набора: (12, группа b) (38, группа a)(12, группа a)

Желаемый результат: (38, группа a) (12, группа a)

(используется только одна группа)

- изменить:Мне нужен алгоритм, чтобы найти минимальное количество групп из набора, как в примере выше.Если у меня будет плохой алгоритм, он выберет (12, группа b) (38, группа a). Это две группы с одинаковыми значениями вместо одной, а не то, что я хочу

Answer 1

Если я правильно понимаю вопрос, это Задача установить крышку

Жадный алгоритм, описанный в ссылке, начинается с группы a, а затем заканчивается, поскольку это уже охватывает все.

Обратите внимание, что в целом он дает только приближение к оптимальному решению.