ДП на подмножествах

Проблема представления подмножеств

Пусть у нас есть некоторое множесьво N = {0, 1, 2, ..., n - 1}, n ≤ 30

Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".

Битовые маски

Что такое битовые маски?

Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае.

Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011₂ = 11₁₀. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа unsigned int, то сможем закодировать любое подмножество, размер которого не больше 32х.

Как работать с множествами, с помощью масок?

Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:

   bool elem_in_subset (unsigned int mask, int pos) {
       return (mask >> pos) & 1;
   }

Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подйдет функция __builtin_popcount (mask), которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответсвует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.

ДП на подмножествах

Задача о гамильтоновом цикле

1) Пусть есть неориентированный взвешанный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти Гамильтонов путь наименьшего веса (простой путь, проходящий через каждую вершину ровно один раз).