Задача о рюкзаке

Поход с ночёвкой в горы над Алматы. Палатка, спальник, еда и вода уже в рюкзаке, и на всё остальное осталось пять килограммов. Хочется взять шестнадцать вещей — от пуховки и горелки до книги и складного стула, — а вместе они весят 8,5 кг. Каждой вещи вы даёте баллы пользы. Какой набор лучший? Наборов 2¹⁶ = 65 536, и с каждой новой вещью их вдвое больше. Таблица ниже находит ответ, заполнив 867 клеток, и потом сама подсказывает, что класть.

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

Рядом счёт простого правила «сначала самое полезное на грамм». Оно набирает 59 баллов: рюкзак наполняется лёгкой мелочью — носками, фонарём, кремом, — а когда очередь доходит до горелки с котелком, для 1,2 кг уже нет места, и 700 граммов так и остаются пустыми. Поменяйте баллы вещам, подвигайте место — и посмотрите, когда жадность угадывает, а когда нет.

Идея

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

Формально: вещи пронумерованы, у i-й вес w_i и польза p_i. best(i, c) — наибольшая польза набора из первых i вещей с весом не больше c. Тогда

а второй вариант есть, только если w_i ≤ c. Такую задачу — каждую вещь можно взять один раз или не брать — называют рюкзаком 0-1: у каждой вещи только два решения, ноль или один. Строки таблицы считаются сверху вниз, каждая только из предыдущей, поэтому порядок заполнения очевиден. Это та же динамика, что в любой задаче на подзадачи: состояние — пара «сколько вещей рассмотрено, сколько места», переход — взять или не взять.

Почему таблица не ошибается

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

Что именно взять

Таблица хранит только числа, но набор по ней восстанавливается без перебора. Встанем в последнюю клетку (n, W) и сравним её с клеткой над ней. Если числа равны, то лучшего результата можно добиться и без вещи n: поднимаемся на строку вверх. Если разные — без вещи n так много не набрать, значит, она взята: поднимаемся на строку и сдвигаемся влево на её вес. Через n шагов набор готов. Это и есть зелёная линия в сцене.

Лучших наборов бывает несколько, и путь назад выбирает один из них: при равенстве он предпочитает не брать вещь. Чтобы восстановить набор, нужна вся таблица — n + 1 строк по W + 1 чисел. Если нужен только ответ, хватит одной строки, но об этом ниже: там ловушка.

Почему не жадно

Жадное правило «сначала самое полезное на грамм» выглядит разумно и иногда даже точно. Если вещи можно резать — насыпать полкилограмма гречки из пакета, — оно и правда даёт лучший результат: каждый грамм места достаётся самому ценному, что ещё осталось. Но рюкзак 0-1 режет только целыми вещами, и место может остаться неиспользованным. Посмотрите на всю картину сразу: для каждой вместимости от нуля до девяти килограммов — лучший рюкзак и жадный.

Сплошная ступенчатая линия — последняя строка таблицы, посчитанная один раз до девяти килограммов: одна строка отвечает для всех вместимостей сразу. Пунктир — жадность, которую пришлось запускать заново для каждой. Она проигрывает на 34 вместимостях из 90, до пяти баллов. Самый наглядный случай — полкилограмма: жадность берёт фонарь, носки и крем — 300 граммов, 12 баллов — и не может взять дождевик за 8 баллов, потому что после мелочи на него не хватает 100 граммов. Таблица кладёт дождевик, фонарь и носки — ровно 500 граммов, 17 баллов.

Бывает и хуже. Две вещи: первая весит 1 грамм и даёт 2 балла, вторая весит ровно всю вместимость W граммов и даёт W баллов. По пользе на грамм первая лучше, жадность берёт её, и вторая уже не влезает: 2 балла против W. Ошибка может быть во сколько угодно раз. У жадности есть простая страховка.

Код

Тот же поход: таблица, путь назад, жадное правило и последняя строка, которая отвечает для любой вместимости до пяти килограммов.

Каждая строка таблицы зависит только от предыдущей, поэтому всю таблицу можно заменить одной строкой и обновлять её на месте. Но порядок обхода в строке решает всё:

Справа налево клетка c − w ещё хранит значение из прошлой строки, то есть лучший набор без текущей вещи, и вещь кладётся не больше раза. Слева направо клетка c − w уже обновлена в этой строке и может сама содержать текущую вещь — и программа с удовольствием кладёт в рюкзак 50 налобных фонарей. Код отличается направлением одного цикла, а решает другую задачу.

Неограниченный рюкзак

Та самая «ошибка» становится правильным алгоритмом, если вещей каждого вида сколько угодно: раскроить рулон ткани на куски стандартной длины, набрать сумму монетами, загрузить вагон одинаковыми ящиками разных типов. Переход тогда смотрит на ту же строку:

и цикл по месту идёт слева направо. Наименьшее число монет для суммы из вводной статьи о динамике — тот же неограниченный рюкзак, только вместо максимума пользы ищут минимум числа монет. В третьей задаче ниже рулон кабеля длиной до 10¹² метров — для него таблица по метрам не поместится ни в какую память, и придётся заметить, что почти весь рулон уходит на один и тот же кусок.

Сколько это стоит

Клеток (n + 1)(W + 1), на каждую — одно сравнение: время O(n·W). Память — O(W), если нужен только ответ, и O(n·W), если нужен набор. Замер подтверждает: при постоянном числе вещей время растёт прямо пропорционально вместимости, а вчетверо больше вещей — вчетверо дольше.

Выглядит как полином, но это обман. W — не количество данных, а число, и записывается оно log₁₀ W цифрами. Допишите к вместимости три нуля — то есть возьмите вес в граммах вместо килограммов, — и вход станет длиннее на три символа, а таблица — в тысячу раз шире. Время, полиномиальное от величины чисел, но экспоненциальное от длины их записи, называют псевдополиномиальным. Вот те же вещи, взвешенные до грамма, как на этикетках, и четыре единицы веса:

При столбце в килограмм каждая вещь, даже носки на 85 граммов, занимает целый килограмм, и в пять столбцов влезает пять вещей: 35 баллов. При 100 граммах вес каждой вещи округляется вверх, и таблица находит 62 балла — меньше 64 из первой сцены, где веса округлены до ближайших ста граммов. С единицей в 10 граммов ответ уже точный, 64 балла, но клеток не 102, а 8517. Каждый следующий знак точности умножает таблицу примерно на десять, а при единице в грамм к ответу он уже ничего не добавляет.

Быстрее не умеет никто: задача о сумме подмножества — рюкзак, где польза вещи равна её весу, — в 1972 году вошла в список 21 NP-полной задачи Ричарда Карпа. Алгоритм, полиномиальный по длине записи чисел, означал бы, что P = NP (об этом вопросе — глава курса). Поэтому для рюкзака выбирают оружие по входу:

• Мало вещей, большие веса. До сорока вещей помогает встреча посередине: 2²⁰ наборов для каждой половины вместо 2⁴⁰.
• Большие веса, маленькие ценности. Таблицу можно повернуть: для каждой суммы ценности хранить наименьший вес, которым её можно набрать. Размер тогда зависит от суммы ценностей, а не от W. Это вторая задача ниже.
• Приближение. Округлим ценности до кратных подходящего числа — и таблица по ценностям станет маленькой. В 1975 году Оскар Ибарра и Чул Ким показали, что так можно получить ответ не хуже (1 − ε) от лучшего за время, полиномиальное и по n, и по 1/ε.
• Отсечения. Ветви и границы перебирают наборы, но отбрасывают ветви, у которых дробная оценка сверху — та самая жадность с кусочком — хуже уже найденного.

Где встречается

Всюду, где есть бюджет и много вариантов его потратить: раскрой листов и рулонов с наименьшими отходами, выбор проектов и вложений при ограниченных деньгах, погрузка транспорта. В 1999 году Стивен Скиена изучил, что ищут посетители его репозитория алгоритмов: среди 75 задач рюкзак оказался девятнадцатым по популярности и третьим среди тех, решения которых нужнее всего, — после суффиксных деревьев и упаковки в контейнеры. Часто рюкзак прячется внутри другой задачи: на какие вопросы экзамена потратить ограниченное время, если они стоят по-разному, какие рекламные ролики поставить в минутный блок.

Рюкзачный шифр

Задачи такого рода математики разбирали ещё в XIX веке: работу Джорджа Мэтьюза «О разбиении чисел» 1897 года считают одной из первых. В 1956 году Ричард Беллман и Стюарт Дрейфус в корпорации RAND решали динамикой «задачу о загрузке груза», где трудность создавали неделимые предметы, — тот же рюкзак. В 1957 году Джордж Данциг описал жадный способ — брать по убыванию ценности на единицу веса — и оценку сверху, которую даёт дробный вариант; ею до сих пор пользуются методы ветвей и границ.

Самая драматичная страница истории — криптография. В 1978 году Ральф Меркл и Мартин Хеллман опубликовали одну из первых систем шифрования с открытым ключом, построенную на сумме подмножества. Секрет — сверхвозрастающая последовательность, где каждое число больше суммы всех предыдущих. Для неё задача о сумме решается жадно: берём самое большое число, которое не больше остатка, — и это единственный правильный выбор. Меркл и Хеллман маскировали такую последовательность умножением по модулю, публиковали замаскированные числа как ключ, а сообщение шифровали суммой тех чисел, которым соответствуют единичные биты. Расчёт был на то, что без маски противнику достаётся общая задача о сумме подмножества с огромными числами, где таблица из этой статьи безнадёжна.

Но в 1982 году Ади Шамир показал, что маскировка выдаёт себя: по одному открытому ключу можно за полиномиальное время найти числа, превращающие его обратно в сверхвозрастающую последовательность. Задача о рюкзаке осталась трудной в общем случае, а вот её частный случай с «замаскированной лёгкостью» оказался лёгким. Отсюда урок: шифру мало, чтобы задача была трудной в худшем случае, — трудными должны быть именно те её экземпляры, которые получаются при шифровании.

Задачи

Первая — рюкзак 0-1 с восстановлением набора: курьер выбирает заказы. Во второй бюджет в тенге так велик, что таблицу придётся повернуть. В третьей рулон кабеля длиной до триллиона метров, и понадобится идея, а не таблица.