Перебор с отсечением

Перебор — это когда мы честно рассматриваем все варианты. У него плохая репутация: кажется, что к нему прибегают, когда не придумали ничего умного.

Это неверно. Перебор — законный инструмент с известной ценой. Вопрос только в том, помещается ли эта цена в отведённое время.

Читать эту таблицу надо в обе стороны. Если в условии написано «$n \le 18$» — это почти прямая подсказка: имеется в виду перебор подмножеств. Если «$n \le 9$» — перестановки. Маленькое ограничение в условии никогда не бывает случайным.

Ещё одна цена — множитель

Вариантов $2^{18} = 262144$, и это немного. Но если для каждого варианта мы делаем ещё цикл по $n$ элементам, получается $2^n \cdot n$ — уже под пять миллионов, а при $n = 20$ и все двадцать.

Поэтому в переборе важно не только количество вариантов, но и что делается внутри. Хорошее правило: считать не с нуля, а обновлять.

Каждое подмножество из $n$ элементов — это выбор «беру / не беру» для каждого. То есть строка из $n$ нулей и единиц. То есть, как мы знаем с прошлого занятия, — число от 0 до $2^n - 1$.

for mask in range(1 << n):        # 1 << n — это 2 в степени n
    for i in range(n):
        if mask >> i & 1:         # взят ли элемент с номером i
            ...

Выражение mask >> i & 1 сдвигает маску вправо на $i$ разрядов и берёт младший бит — это ровно $i$-я цифра двоичной записи.

Как убрать внутренний цикл

Если нужны суммы всех подмножеств, считать каждую заново расточительно. Заметим: у маски mask уберём младший установленный бит — получится маска, для которой сумма уже посчитана.

sums = [0] * (1 << n)
for mask in range(1, 1 << n):
    low = mask & -mask                       # младший установленный бит
    index = low.bit_length() - 1             # его номер
    sums[mask] = sums[mask ^ low] + a[index]

Теперь на каждое подмножество приходится одно сложение вместо цикла. Это тот самый переход от $2^n \cdot n$ к $2^n$.

Трюк mask & -mask выделяет младший единичный бит — стоит просто запомнить.

В условии написано: «$n$ от 1 до 9». Что это скорее всего означает?

У масок есть недостаток: они перебирают всё подряд и не дают остановиться на полпути. Рекурсия даёт.

def go(index, current):
    if index == n:
        ...            # набор собран целиком
        return
    go(index + 1, current)              # не берём a[index]
    go(index + 1, current + a[index])   # берём

Тех же $2^n$ листьев, но теперь мы находимся внутри частично собранного решения, и про него уже кое-что известно. Значит можно не спускаться дальше, если ясно, что ничего хорошего внизу нет. Это и называется отсечением.

Три вида отсечений

Нарушено ограничение. Вес уже больше вместимости рюкзака — добавлять предметы бессмысленно, дальше будет только тяжелее.

if weight + weights[index] <= capacity:
    go(index + 1, weight + weights[index], value + values[index])

Не дотянемся до цели. Заранее посчитаем сумму всех оставшихся чисел. Если текущее значение отличается от цели больше, чем на эту сумму, — цель недостижима, что бы мы ни делали.

Ответ уже найден. Если задача спрашивает «существует ли», после первой удачи можно прекращать поиск целиком.

Что делает отсечение законным

Отсечение обязано отбрасывать только заведомо безнадёжные ветки. Проверка та же, что была в занятии про окно: если я отбрасываю ветку, точно ли в ней не может оказаться ответ?

Отсечение «вес превысил вместимость» законно, потому что вес только растёт. Если бы веса могли быть отрицательными, оно стало бы неверным — и ответ бы молча испортился.

Сколько всего подмножеств — включая пустое — у множества из 20 элементов? Введите целое число.

Есть приём, который превращает недостижимый перебор в достижимый. Пусть чисел 34 и нужно посчитать наборы с суммой $s$. Вариантов $2^{34}$ — это семнадцать миллиардов, нельзя.

Разобьём список пополам. В каждой половине по 17 чисел, то есть по $2^{17} = 131072$ набора. Переберём их отдельно — это быстро.

Теперь любой набор целого списка — это пара «набор слева плюс набор справа». Значит нужно посчитать пары с суммой $s$. Складываем суммы левой половины в словарь подсчётов, идём по суммам правой и для каждой спрашиваем, сколько левых дополняют её до $s$.

left = Counter(subset_sums(a[:half]))
total = 0
for value in subset_sums(a[half:]):
    total += left.get(s - value, 0)

Было $2^{34}$, стало $2 \cdot 2^{17}$ — в шестьдесят пять тысяч раз меньше. Приём так и называется: встреча посередине.

Если вместо точного равенства нужно «не больше $s$», словарь заменяется на отсортированный список и двоичный поиск — ровно то, чем мы занимались на тридцать первом занятии.

Отсечение, меняющее ответ. Самая опасная: программа работает быстро и выдаёт неверный результат. Каждое отсечение проговаривайте вслух — почему в отброшенной ветке точно нет ответа.

Забытый откат. В переборе с возвратом состояние меняют перед спуском и обязаны вернуть после. Пропущенный откат портит все последующие ветки, и ошибка проявляется где-то далеко от места, где сделана.

Прерванный цикл с недосчитанным значением. break выходит из цикла, оставляя переменную в промежуточном состоянии. Если её потом проверяют, сравнение идёт с полуфабрикатом.

Внутренний цикл на каждый вариант. $2^n \cdot n$ вместо $2^n$. При $n = 20$ разница между «успел» и «не успел».

Оценка на глазок. «Ну, $2^{30}$ — это же всего миллиард». Миллиард операций в Python — это минуты. Считайте до того, как писать.

Как проверять себя

• самое маленькое $n$ — единица, а иногда и ноль элементов;
• пустой набор — подходит он по условию или нет;
• все элементы одинаковые — там вылезают ошибки с подсчётом одинаковых наборов;
• самое большое $n$ из условия — успевает ли решение по времени.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Первым делом смотрите на ограничение: 18 — это подмножества, 9 — перестановки, 200 — тройной цикл, 34 — встреча посередине. Ограничение и есть подсказка.

И прежде чем добавить отсечение, скажите себе одним предложением, почему оно ничего не теряет.

Задача: «дан список из $n \le 18$ натуральных чисел; посчитайте, сколько подмножеств имеют сумму ровно $s$».

Ученик написал перебор по маскам и добавил отсечение, чтобы не досчитывать заведомо большие суммы:

n, s = map(int, input().split())
a = list(map(int, input().split()))

count = 0
for mask in range(1 << n):
    total = 0
    for i in range(n):
        if mask >> i & 1:
            total += a[i]
        if total >= s:
            break
    if total == s:
        count += 1

print(count)

Постройте вход, на котором программа ошибается, объясните, что именно пошло не так, и предложите исправление.