ДП на подмножествах — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Битовые маски)
(Битовые маски)
Строка 5: Строка 5:
 
== Битовые маски ==
 
== Битовые маски ==
 
Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае. <br><br>
 
Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае. <br><br>
Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х. Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:<br><br>
+
Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х. Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:<br>
<code>
+
    '''bool''' elem_in_subset ('''unsigned int''' mask, '''int''' pos) {
bool element_in_subset (unsigned int mask, int pos) {
+
        return (mask >> pos) & 1
return (mask >> pos) & 1U;
+
    }
}
+
hkjh
</code>
 

Версия 19:07, 30 апреля 2020

Описание проблемы

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

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

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

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

Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 10112 = 1110. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа unsigned int, то сможем закодировать любое подмножество, размер которого не больше 32х. Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:

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

hkjh