Backtracking с отсечениями — распределение задач между работниками РАЗБОР

Backtracking — старая, простая и часто единственно применимая техника для задач, где других путей не видно: NP-полные / NP-трудные задачи, переборные комбинаторные конструкции, точное покрытие. Если линейные техники (DP, жадный, бинпоиск) не подходят, а размер входа маленький — можно перебрать. Главное — отсекать.

Эта задача — учебный кейс. Условие звучит безобидно: распределить $n$ задач между $k$ работниками так, чтобы максимальная нагрузка была минимальна. Сложность — задача NP-трудная (вариант задачи о разбиении). На малом $n$ (до $\sim 12$–$16$) перебор работает; ключ — три отсечения, превращающих наивный $k^n$ в реалистичные $\sim 10^6$ узлов рекурсии.

---

Что дано

Есть $n$ задач длительностями $a_1, \ldots, a_n$ и $k$ работников. Каждая задача должна быть назначена ровно одному работнику. Работник может получить любое число задач (включая ноль). Нагрузка работника — сумма длительностей всех его задач. Найти минимально возможный максимум нагрузок при оптимальном распределении.

Ограничения

• $1 \le k \le n \le 12$.
• $1 \le a_i \le 10^9$.

Формат ввода

n k
a_1 a_2 ... a_n

Формат вывода

Одно целое число — минимально возможный максимум нагрузок.

Пример A

4 2
3 1 2 4

Разбиения и максимумы:

• $\{3, 1\} \mid \{2, 4\}$: $\max(4, 6) = 6$.
• $\{3, 2\} \mid \{1, 4\}$: $\max(5, 5) = 5$.
• $\{3, 4\} \mid \{1, 2\}$: $\max(7, 3) = 7$.
• $\{4, 1\} \mid \{3, 2\}$: $\max(5, 5) = 5$.
• … и так далее.

Минимум — $5$.

Пример B

6 3
1 2 3 4 5 6

Сумма $21$, средняя нагрузка $7$. Распределение $\{6, 1\} \mid \{5, 2\} \mid \{4, 3\}$ — максимум $7$. Меньше быть не может (любой работник, получивший задачу $6$, имеет нагрузку $\ge 6$; на двух оставшихся работников приходится $15$, средняя $7.5$, кто-то имеет $\ge 8$ — нет, ошибаюсь: 7+8 = 15 или 6+9 — но без $6$ распределим 15 на двоих, минимум максимума = $\lceil 15/2 \rceil = 8$? Хм, $\{5, 2, 1\}$ = 8 и $\{4, 3\}$ = 7, максимум 8. Аналогично если 6+1 = 7, проверим $\{5,3\} = 8$, $\{4,2\} = 6$ — максимум 8. Значит, нужно вернуться к $\{6,1\}, \{5,2\}, \{4,3\}$ с максимумом 7).

Ответ — $7$.

---

Идея решения

Прямой перебор. Каждой задаче независимо назначаем одного из $k$ работников. Получаем $k^n$ конфигураций; для каждой считаем максимум, берём минимум. На $n = 12, k = 4$ — $4^{12} \approx 1.7 \cdot 10^7$ — терпимо. На $n = 16, k = 4$ — $4^{16} \approx 4 \cdot 10^9$ — TL.

Отсечения превращают этот наивный перебор в практически быстрый. Три ключевых:

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

Отсечение 2: branch-and-bound. Хранится текущий лучший найденный ответ best. В каждом узле перебора, перед назначением задачи $i$ работнику $j$, проверяем: если новая нагрузка $\text{loads}[j] + a_i \ge \text{best}$ — пропускаем эту ветку. Любое продолжение даст максимум $\ge \text{best}$, что не улучшит результат.

Отсечение 3: симметрия по одинаковым работникам. Если в данный момент несколько работников имеют одинаковую текущую нагрузку — назначать новую задачу можно только первому из них (по индексу). Остальные дадут эквивалентные ветки перебора, рассчитанные через зеркальную перестановку работников. Это отсекает $k!$ дубликатов в листьях дерева.

---

Эффект от отсечений

Симметрийное отсечение — самое эффективное: при равных работниках оно сразу режет $k!$-ветви. Branch-and-bound даёт основной вклад при разных $a_i$.

---

Алгоритм

прочитать n, k, a[0..n-1]
отсортировать a по убыванию

best ← sum(a)          # худший случай: один работник делает всё
loads[0..k-1] ← 0

функция backtrack(i):
    если i == n:
        cur_max ← max(loads)
        если cur_max < best:
            best ← cur_max
        return

    seen ← пустое множество
    для j от 0 до k-1:
        если loads[j] ∈ seen:
            продолжить                                    # симметрия
        seen ← seen ∪ {loads[j]}
        если loads[j] + a[i] >= best:
            продолжить                                    # branch-and-bound
        loads[j] ← loads[j] + a[i]
        backtrack(i + 1)
        loads[j] ← loads[j] - a[i]

backtrack(0)
вывести best

Семантика best — лучший найденный максимум на момент рассмотрения. Старт с sum(a) гарантирует, что любое полное распределение даст не хуже.

---

Руками на примере A

$n = 4$, $k = 2$, $a = [3, 1, 2, 4]$. Сортируем по убыванию: $a = [4, 3, 2, 1]$. best = 10 (сумма).

backtrack(i=0), loads=[0, 0]
  Задача a[0]=4:
    seen={}, рассмотрим j=0:
      loads[0] + 4 = 4 < best(10) — продолжаем
      loads = [4, 0]
      backtrack(i=1)
        Задача a[1]=3:
          seen={}, рассмотрим j=0:
            loads[0] + 3 = 7 < 10 — продолжаем
            loads = [7, 0]
            backtrack(i=2)
              Задача a[2]=2:
                seen={}, j=0: loads[0]+2=9<10 — продолжаем; loads=[9,0]
                  backtrack(i=3)
                    Задача a[3]=1:
                      j=0: loads[0]+1=10 >= best(10) — пропуск
                      j=1: 0 не в seen; loads[1]+1=1 < 10 — продолжаем; loads=[9,1]
                        backtrack(i=4): cur_max=9, best=9
                      откат: loads=[9,0]
                  откат: loads=[7,0]
                seen={9}; j=1: 0 не в seen; loads[1]+2=2 < 9 — продолжаем; loads=[7,2]
                  backtrack(i=3)
                    Задача a[3]=1:
                      j=0: loads[0]+1=8 < 9 — продолжаем; loads=[8,2]
                        cur_max=8, best=8
                      откат; j=1: 2 не в seen; loads[1]+1=3 < 8 — продолжаем; loads=[7,3]
                        cur_max=7, best=7
                      откат
                  откат
            откат
          j=1: 0 не в seen; loads[1]+3=3 < 7 — продолжаем; loads=[4,3]
            backtrack(i=2)
              Задача a[2]=2:
                j=0: 4+2=6 < 7 — продолжаем; loads=[6,3]
                  backtrack(i=3)
                    a[3]=1: j=0: 6+1=7 >= 7 — пропуск
                            j=1: 3 не в seen; 3+1=4 < 7 — loads=[6,4]
                              cur_max=6, best=6
                  откат
                j=1: 3 не в seen; 3+2=5 < 6 — продолжаем; loads=[4,5]
                  backtrack(i=3)
                    a[3]=1: j=0: 4+1=5 < 6 — loads=[5,5]; cur_max=5, best=5
                            j=1: 5 ∈ seen{4} ? нет; 5+1=6 >= 5 — пропуск
                  откат
            откат
      откат
    j=1: 0 ∈ seen{0} — пропуск (симметрия)

Итог — best = 5. ✓

Симметрийное отсечение на самом верхнем уровне обрезает зеркальную половину дерева; branch-and-bound отсекает каждый раз, когда добавление задачи к какому-то работнику не улучшит результат.

---

Код решения

Комментарии по реализации

• best как массив длины 1 в Python. Из-за замыкания и неизменяемости int. В C++ — обычная глобальная переменная.
• seen — set в обоих языках. При $k \le 12$ можно было обойтись массивом, но set — компактнее и читаемее. На производительность не влияет.
• Сортировка по убыванию обязательна. Без неё branch-and-bound отсекает в разы меньше — большие задачи добавляются на поздних уровнях, когда уже распределены сотни мелких комбинаций.
• Тип нагрузки — long long. При $n = 12$, $a_i$ до $10^9$ сумма до $1.2 \cdot 10^{10}$. int переполнится.
• < vs <= в branch-and-bound. loads[j] + a[i] >= best — строго $\ge$. Если поставить $>$, можно пропустить ветку, дающую ровно best — но она ровно best, не улучшение, всё равно бесполезна. Условие $\ge$ — правильное, $>$ тоже работает (просто менее агрессивно отсекает).

---

Проверка на примерах

Пример A

$n = 4$, $k = 2$, $a = [3, 1, 2, 4]$. Распределение $\{4, 1\} \mid \{3, 2\}$ даёт максимумы $5, 5$. Минимум $\max$ = 5. ✓

Пример B

$n = 6$, $k = 3$, $a = [1, 2, 3, 4, 5, 6]$. Распределение $\{6, 1\} \mid \{5, 2\} \mid \{4, 3\}$ даёт нагрузки $7, 7, 7$. Минимум $\max$ = 7. ✓

---

Крайние случаи

• $k = 1$. Один работник делает всё — ответ $\sum a_i$. Backtracking работает без отсечений, симметрия не активируется, branch-and-bound — да: после первого полного прохода best = $\sum a_i$, дальше всё отсекается. Узлов в дереве — $n$.
• $k = n$. Каждому достанется одна задача. Ответ $\max a_i$. Симметрия отсекает почти всё дерево: после первого назначения «$a_0$ → работник 0» все работники с нагрузкой $0$ эквивалентны, остаётся один путь.
• $k > n$. По условию $k \le n$. Если допустить $k > n$ — лишние работники не нагружены, ответ $\max a_i$. Симметрия снова режет: эквивалентные пустые работники игнорируются.
• Все $a_i$ равны. Ответ — $a_1 \cdot \lceil n/k \rceil$. Симметрия отсекает все перестановки распределения, branch-and-bound — все худшие.
• Один большой $a_i$. Например, $a = [100, 1, 1, 1, 1]$, $k = 2$. Ответ — $100$ (большая задача всё равно у одного работника, мелкие — у другого, нагрузка большого диктует ответ).

---

Типичные ошибки

1. Не сортировать по убыванию. Сортировка по возрастанию (или вообще без сортировки) даёт катастрофически меньшее отсечение. На $n = 12$ это разница между $10^3$ и $10^6$ узлов.
2. Забыть про симметрию. Без неё на $n = 12, k = 6$ дерево раздувается в $k!$ раз. Симметрия — самое мощное отсечение для NP-трудных задач с одинаковыми контейнерами.
3. best инициализирован 0. Тогда branch-and-bound отсекает всё, и ответ остаётся 0 — WA. Правильная инициализация — sum(a) или INF (но INF менее агрессивно отсекает).
4. Восстанавливать состояние неполно. После рекурсии нужно явно вычесть a[i] из loads[j]. Забыли — другие ветки получат «отравленные» данные.
5. Использовать int для нагрузок в C++. Переполнение при $n \cdot \max a \sim 10^{10}$.
6. Симметрия по loads[j] vs по индексу. Правильно — по значению текущей нагрузки. Если делать «не назначать на $j$, если $j > 0$ и loads[j] == loads[j-1]» — это работает только если массив отсортирован по нагрузкам, что не гарантируется при динамических изменениях. Через set seen — корректно всегда.
7. Считать max(loads) слишком часто. В коде выше — только в листе перебора, после полного распределения. Если считать на каждом узле — добавляется $O(k)$ накладных, асимптотика растёт. Оптимизация: поддерживать cur_max рекурсивно, обновляя только при изменении.
8. Применять backtracking, когда задача — поли-номиально решаемая. Если в условии «равные суммы», или $a_i$ ограничены маленьким числом — задача решается DP (bitmask DP по подмножествам). Backtracking — последняя надежда, не первая.

---

Сложность

• Время. В худшем случае — экспоненциальное, $O(k^n)$ без отсечений. С полным набором отсечений — на практике $\sim 10^4$–$10^6$ узлов при $n \le 12$, в C++ это десятки мс, в Python — секунды.
• Память. Стек рекурсии $O(n)$, массив нагрузок $O(k)$. Итого $O(n + k)$.

Главная особенность — нет точной оценки сложности с отсечениями. На «приятных» входах работает мгновенно, на специально подобранных «злых» — может приблизиться к наивному $O(k^n)$. Поэтому в задачах с большим $n$ или гарантированно «злыми» тестами backtracking — рискованный выбор.

---

Связанные задачи

• Bitmask DP по подмножествам $a_i$. Альтернатива backtracking-у для той же задачи: $dp[\text{mask}]$ = минимальное число работников, чтобы покрыть подмножество $\text{mask}$ при ограничении на максимальную нагрузку. Бинпоиск по ответу + DP за $O(3^n)$ на проверку. Менее эластична к большим $a_i$, но детерминированная.
• Knapsack / задача о рюкзаке с branch-and-bound. Та же идея: текущая лучшая граница, отсечение нижних оценок. Branch-and-bound — общий метод, backtracking с отсечениями — частный случай.
• Раскраска графа в $k$ цветов (Chromatic number). NP-трудная, backtracking по вершинам, отсечения: симметрия по цветам, branch-and-bound, эвристика выбора следующей вершины (max-degree first).
• Точное покрытие множества (Exact Cover). Algorithm X / Dancing Links — структура данных для эффективного backtracking-а с сохранением состояния.
• N ферзей. Классическая backtracking-задача. Симметрии (повороты, отражения) могут сократить дерево в 8 раз; пропуск симметричных стартовых позиций — дисциплинированный приём.

---

Итого

• Идея: перебираем все распределения задач по работникам с тремя отсечениями.
• Отсечения: (1) сортировка по убыванию, (2) branch-and-bound по best, (3) симметрия по одинаковым нагрузкам.
• Сложность: в худшем $O(k^n)$, на практике после отсечений $\sim 10^4$–$10^6$ узлов.
• Главные ловушки: забыть сортировку, забыть симметрию, начать best с 0, забыть восстановить состояние, int вместо long long.
• Когда не подходит: $n$ большое (> 16), есть полиномиальный алгоритм (DP), нужна гарантия по времени на адверсариальных тестах.

Источник задачи: формат задач Иннополис Open на backtracking с отсечениями (полоса ~1600).