ДП на подмножествах — различия между версиями
(→Битовые маски) |
(→Битовые маски) |
||
| Строка 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>. Таким образом, с помощью числа типа unsigned int | + | Напрмер, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа unsigned int, то сможем закодировать любое подмножество, размер которого не больше 32х. |
Версия 18:45, 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х.
