Перебор подмножеств с битовыми масками
Перебирайте все подмножества через целые числа
«Перебор подмножеств с битовыми масками» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Подмножества как числа
Каждому подмножеству из n элементов соответствует одно целое число. Считайте от 0 вверх: биты каждого числа точно определяют, какие элементы входят в подмножество. 🙂
Сколько существует подмножеств
У множества из n элементов есть 2^n подмножеств. Поэтому перебор целого числа от 0 до 2^n минус 1 посещает каждое подмножество ровно один раз.
for mask in range(1 << n):
pass # mask is one subsetСдвиг 1 << n задаёт количество
Сдвиг 1 << n равен 2 в степени n. Это простой и быстрый способ записать верхнюю границу цикла перебора подмножеств.
Прочитайте бит i
Чтобы проверить, входит ли элемент i в подмножество, проверьте его бит с помощью маски и единицы, сдвинутой влево на i позиций. Ненулевой результат означает, что элемент включён.
if mask & (1 << i):
take(items[i])Соберите список выбранных элементов
Пройдите по каждой позиции бита и соберите элементы, у которых бит установлен. Так одна маска превращается в конкретное представляемое ею подмножество.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Пустое и полное множества
Маска 0 — это пустое подмножество, а маска из одних единиц — полное множество. Оба варианта обрабатываются автоматически, поскольку цикл охватывает все значения.
Просуммируйте элементы подмножества
Внутри цикла складывайте выбранные элементы, чтобы вычислить оценку каждого подмножества. Это основа многих небольших решений методом полного перебора.
total = sum(v[i] for i in range(n) if mask & (1 << i))Подсчитайте установленные биты
Количество выбранных элементов равно числу единичных битов в маске, то есть её количеству единичных битов. В Python выражение bin(mask).count('1') вычисляет его мгновенно.
size = bin(mask).count("1")Следите за ограничением
Поскольку существует 2^n подмножеств, этот метод подходит только для небольших значений n. Практический предел полного перебора — примерно n, равное 20.
Почему побитовые маски эффективны
Один цикл по целым числам заменяет запутанные вложенные циклы, а побитовые операции выполняются быстро. Код остаётся коротким, понятным и удобным для тестирования.
Шаблон для повторного использования
Переберите маску, расшифруйте её биты, вычислите оценку подмножества и сохраните лучший результат. Запомните этот шаблон — и многие задачи о подмножествах станут обычной практикой.
Быстрая проверка
Вам нужно проверить, входит ли элемент i в подмножество, закодированное маской.
Итоги
Перебирайте маску от 0 до 2^n минус 1, читайте биты с помощью маски и единицы, сдвинутой влево, и вычисляйте оценку каждого подмножества. Это простой полный перебор для небольших значений n. 🚀
Часто задаваемые вопросы
Урок «Перебор подмножеств с битовыми масками» бесплатный?
Да — полный текст урока «Перебор подмножеств с битовыми масками» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Перебор подмножеств с битовыми масками»?
Перебирайте все подмножества через целые числа Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Перебор подмножеств с битовыми масками»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Полный перебор — допустимая стратегия
- Перебор с itertools
- Перебор подмножеств с битовыми масками
- Разумное сокращение пространства поиска