Участник:Aimly/Packing=MaxClique — Решение Бескровного А.

Материал из DISCOPAL
Перейти к: навигация, поиск

Сделаем следующий переход: подмножество -> вершина графа. Между двумя вершинами такого графа проведено ребро, если множества не пересекаются. Понятно, что тогда задача об упаковке сведется к задаче поиска максимальной клики в построенном нами графе. Итак всего в множестве n элементов и полином от n подмножеств. Для каждой пары подмножеств наличие ребра между соответствующими им вершинами проверяется за время, не большее, чем за n*n (в каждом подмножестве не больше n элементов, для каждого элемента первого подмножества нужно проверить не больше, чем n элементов второго подмножества). Всего нужно проверить . пар, а это тоже полином от n. Мы получили граф с ребрами за полином от n.