Разбор первой задачи из олимпиады «Я-Профессионал», трек “Искусственный интеллект”. 2025 год

Первый пост из этой серии статей. Первые три задачи будут разминочными перед настоящим адом :)

Описание задачи:

В контексте машинного обучения, особенно при работе с последовательностями, необходимо эффективно обрабатывать данные переменной длины в параллельных вычислениях. Для этого можно дополнять короткие последовательности «пустыми» значениями до нужной длины, однако при этом расходуются дополнительная память для хранения и ценные вычислительные ресурсы на обработку «пустых» значений. В качестве альтернативы можно использовать взаимодополнение последовательностей, чтобы свести «пустые» значения к минимуму или избежать их вовсе. Ваша задача — упаковать $n$ объектов разных размеров в минимальное количество контейнеров с фиксированной вместимостью $c$.

Дополнительное описание

Перед разбором стоит уточнить формат ввода и вывода, а также привести один пример.

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

В первой строке дано значение $c$ — вместимость каждого контейнера, $c \in [1, 50]$.

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

В первой строке — минимальное количество контейнеров $k$, в которое можно упаковать данные объекты.
Во второй строке дано значение $n$ — количество объектов, $n \in [1, 400]$.
В третьей строке $n$ значений через пробел — размер каждого объекта $ \in [1, c]$.

Пример:

Ввод Вывод
10 2
5
4 5 6 3 2

Решение

Данная задача может показаться лёгкой, но это лишь на первый взгляд. От нас требуют уложить $n$ элементов в минимальное количество контейнеров с заранее заданным объёмом, и решение приходит к нам почти мгновенно: жадный алгоритм!

Для начала отсортируем объекты по убыванию, а затем для каждого из них попытаемся найти первый контейнер, в который он поместится. Если подходящего контейнера не найдётся, откроем новый. Вот и вся идея решения. Ниже приведена реализация на языке Python:

def ffd(c: int, n: int, objects: list[int]) -> int:
    objects.sort(reverse=True)  # Сортируем объекты в порядке убывания

    containers_count = 0  # Текущее количество использованных контейнеров
    containers = [0] * n  # Заполнённость контейнеров (в худшем случае каждый объект займёт отдельный контейнер)

    for i in range(n):
        j = 0

        # Проходим по существующим контейнерам и вставляем объект в первый, который способен вместить его
        while j < containers_count:
            if containers[j] >= objects[i]:
                containers[j] -= objects[i]
                break
            j += 1

        # Если подходящий контейнер не найден, создаём новый
        if j == containers_count:
            containers[containers_count] = c - objects[i]
            containers_count += 1

    return containers_count

if __name__ == '__main__':
    c = int(input())
    n = int(input())
    objects = list(map(int, input().split()))
    print(ffd(c, n, objects))

Прекрасно! Это решение проходит все тесты, и мы получаем 10/10 баллов, однако оно не является корректным...

Я привёл реализацию с асимптотической сложностью $O(n^2)$, однако существует вариант сделать это за $O(n\log{n})$ с помощью сбалансированного бинарного дерева.

Здесь только боль и ничего больше, или же почему у этой задачи нет простого решения?

Сразу раскрою все карты: эта задача в литературе называется Bin Packing Problem, относится к классу задач оптимизации и является NP-Hard (то есть гарантировать нахождение оптимального решения за полиномиальное время крайне сложно).

Представленная мной эвристика (аппроксимационный, приближённый алгоритм) имеет название First-Fit Decreasing (FFD), что дословно переводится как «первый подходящий элемент по убыванию». Этот алгоритм гарантирует допустимое решение (каждый контейнер не будет заполнен более чем до $c$), но при этом не обеспечивает оптимального результата.

Математическая модель задачи с использованием целочисленной линейной программы (ILP)

  1. Пусть $x_{ij}$ — бинарная переменная, равная 1, если объект $i$ размещён в контейнере $j$, и 0 иначе.
  2. Пусть $y_{j}$ — бинарная переменная, равная 1, если контейнер $j$ используется, и 0 иначе.
  3. Пусть $S$ — множество объектов, а $c$ — вместимость контейнера.
  4. Пусть $OPT(S, c)$ — оптимальное решение задачи.

Задача: $$\min\sum_{j=1}^{m} y_{j},$$
где $m \geqslant n$ (например, можно взять $m=n$, так как в худшем случае каждый объект может оказаться в отдельном контейнере).

Ограничения:

  1. Каждый объект должен быть размещён ровно в одном контейнере: $$\sum_{j=1}^{m} x_{ij} = 1 \hspace{1cm} \forall i = 1, \ldots, n.$$
  2. Суммарный размер объектов в контейнере $j$ не превышает $c$, если контейнер используется: $$\sum_{i=1}^{n} s_{i} x_{ij} \leqslant c\, y_{j} \hspace{1cm} \forall j = 1, \ldots, m.$$
  3. Все переменные бинарны: $x_{ij}, y_{j} \in {0,1}$.

Решение ILP для $n \leqslant 400$ может быть вычислительно затруднительным, поэтому мы используем эвристику FFD.

Аппроксимационная оценка

Нижняя оценка, приведённая Dósa, выглядит следующим образом. Рассмотрим две конфигурации контейнеров:

Если оптимальное решение включает 4 копии $B_{1}$ и 2 копии $B_{2}$, тогда FFD выдаст следующую конфигурацию контейнеров:

Общее количество контейнеров получается равным 8, тогда как оптимальное решение содержит всего 6 контейнеров. При этом алгоритм укладывается в верхнюю оценку: $$ 6\cdot\frac{11}{9} + \frac{6}{9} = 8.$$

Обобщим этот пример для $OPT(S, c)$. В оптимальном решении имеется $6k+4$ контейнеров типа $B_{1}$ и $3k+2$ контейнеров типа $B_{2}$, а для FFD требуется не менее $11k+8$ контейнеров, то есть: $$ FFD(S, c) \geq \frac{11}{9}(6k+4+3k+2) + \frac{6}{9}. $$

Таким образом, получаем аппроксимационную оценку этой эвристики: $$ FFD(S, c) \leqslant \frac{11}{9}OPT(S, c) + \frac{6}{9}. $$

А есть ли что-то получше?

Ответ: да. Существует множество эвристик, которые имеют лучшую оценку, чем FFD. Даже существуют точные алгоритмы, например, Improved Bin Completion, разработанный Schreiber и Korf в 2013 году. Но, на мой взгляд, FFD является во многих случаях лучшим выбором, учитывая цена/качество точность и относительную простоту реализации.

Источники

Improved Bin Completion
The Tight Bound of FFD
FFD