Динамика по подмножествам, по профилю (3 декабря 2024)

  1. Задача: покрасить вершины графа в минимальное число цветов
    1. Напоминание: умеем за 3n + 2nn2
    2. 2nn2 → 2n (можно ещё раз, если уже было)
    3. Алгоритм перебора всех максимальных по включению за 3n/3 = 1.44n
    4. Покраска вершин, описание решения за O(2.44n). Доказательство: (1+1.44)n

  2. Задачи на подмножествах
    1. [есть в прошлой практике!] Рюкзак (Set Cover: покрыть множество {0,1,...,n-1} минимальным числом множеств из набора A1,...,Am
    2. Перевёрнутая битовая запись числа (001101 → 101100)
  3. Meet-In-The-Middle
    1. Решение задачи о рюкзаке
      1. Выбрать подмножество заданной суммы за 2n/2 (2 способа: сортировка, хеш-таблица)
      2. Выбрать подмножество веса до W максимальной стоимостью за 2n/2n (сортировка и префиксный минимум)
    2. Решение задачи о поиске максимальной клики (подводка к кликам: выбрать дружную компанию на день рождения)
      1. За 2n
      2. Классический Meet-In-The-Middle. 2n/2n (до 2n/2 можно не оптимизировать)
      3. Перебор (две ветки: берём или не берём) с отсечением запоминанием + док-во того, что не более 2n/2 состояний
− Перерыв −
  1. DP и скошенный профиль без рекурсии рекурсию (задача про доминошки)
    1. Вспоминаем задачу, решение.
    2. Пишем код без рекурсии по изломаному профилю.
    3. Замечаем, что можно ещё делать то же самое по прямому (матрица в степени).

  2. Покраска за 2nn
    1. постановка задачи, предподсчёт
    2. формула включения-исключения

  3. Максимальная клика быстрее 2n/2