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

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

Ключевые вопросы параграфа

• Почему жадный алгоритм не подходит для задачи о рюкзаке?
• Как с помощью рекурсии и мемоизации находить решение без перебора всех подмножеств?
• В чём разница между рекурсивной и итерационной реализациями алгоритма?

Условие

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

Естественная жадная стратегия — взять самый тяжелый слиток, на который хватает вместимости рюкзака, и повторно проверить, а осталось ли место на ещё один слиток.

При наборе слитков, приведённом выше, и рюкзаке вместимостью «жадный» алгоритм выбирает слитки весом и . Однако оптимальное решение — использовать слитки весом 4, 6 и 10!

• Входные данные: Первая строка ввода содержит целое число (вместимость рюкзака) и количество золотых слитков . В следующей строке приведены целых чисел , которые определяют вес золотых слитков.
• Выходные данные: Максимальный вес золотых слитков, который можно уместить в рюкзак вместимостью .
• Ограничения: ; ; .

Пример 1

Сумма веса первого и последнего слитков равна .

Вместо решения изначальной задачи проверим, можно ли выбрать поднабор слитков с общим весом , если имеем слитков весом (мы перешли на отсчёт с нуля)?

Упражнение

Продемонстрируйте, как можно использовать это решение для выполнения задачи «Максимальное количество золота».

Первый вариант решения

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

• Случай 1: Если , тогда рюкзак вместимостью может быть заполнен первыми слитками.
• Случай 2: Если , тогда мы можем убрать слиток с весом из рюкзака, и вес оставшихся слитков составит . Таким образом, рюкзак с вместимостью можно полностью заполнить первыми слитками.

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

Обратите внимание, что при второе выражение не имеет смысла.

Кроме того, и для любого .

В целом

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

1Knapsack([w[0],…,w[n−1]],W):
2    pack = two-dimensional array of size (W+1)×(n+1)
3    initialize all elements of pack to false
4    pack[0][0] = true
5    for i from 1 to n:
6        for w from 0 to W:
7            if w[i-1] > w:
8                pack[w][i] = pack[w][i−1]
9            else:
10                pack[w][i]←pack[w][i−1] OR pack[w−w[i−1]][i−1]
11    return pack[W][n]

В приведённой ниже двумерной таблице представлены результаты вызова Knapsack([1,3,4], 8. F и T означают значения false и true.

Второй вариант решения

Другое решение будет заключаться в анализе поднаборов всех слитков. Наша цель — найти поднабор из слитков с общим весом .

Простой подход к такой задаче — просматривать все поднаборы и проверять, есть ли поднабор с весом . Так как каждый слиток можно или пропустить, или взять, каждый поднабор из трёх слитков, который мы анализируем (, , ), можно представить сине-красным бинарным вектором:

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

• Если первый бит — синий, то он соответствует синему горизонтальному сегменту сетки, связывающему с .
• Если первый бит — красный, то он соответствует красному сегменту сетки, связывающему с .
• Обработав первые битов, мы получаем сине-красный путь от до некого узла на сетке.
• Если следующий бит — синий, мы связываем с .
• Если следующий бит — красный, мы связываем с , как показано ниже для вектора 101:

Рисунок ниже демонстрирует пути, которые соответствуют всем восьми бинарным векторам с длиной 3.

Теперь мы накладываем все эти восемь путей на одну сетку:

Мы классифицируем узел на сетке как истинный («true») при наличии пути от к на рисунке выше. В других случаях — ложный («false»). Теперь мы можем полностью заполнить рюкзак с вместимостью поднабором из первых слитков, если узел — истинный («true»). Узел будет истинным в случаях, если в него проходит или синее, или красное ребро. То есть, если или истинны. Это наблюдение приводит нас к предыдущему рекуррентному соотношению и к такому же решению с динамическим программированием.

Третий вариант решения

А вот ещё один вариант решения, который основан на мемоизации. Приведённый ниже псевдокод рекурсивно вычисляет рекуррентное соотношение из решения 1:

1RecursiveKnapsack([w[0],…,w[n−1]],w,i):
2    if i=0 and w=0:
3        return true
4    else if i=0 and w>0:
5        return false
6    else if i>0 and w_[i-1]>w:
7        return RecursiveKnapsack([w[0],…,w[n−1]],w,i−1)
8    else:
9        return RecursiveKnapsack([w[0],…,w[n−1]],w,i−1) OR   RecursiveKnapsack([w[0],…,w[n−1]],w−w[i−1],i−1)

Вызов RecursiveKnapsack([w_0, ..., w_{n-1}],W, n) решает задачу, но он сильно замедлен из-за необходимости перевычислять одни и те же значения снова и снова.

Чтобы это продемонстрировать, рассмотрим рюкзак с вместимостью и слитков с весом , , . Вызов RecursiveKnapsack([1, 1, 1], 4, 3) создаёт рекурсивное дерево, приведённое ниже — каждый узел показывает значения .

Даже в этом простом примере значение вычисляется дважды. С 20 слитками рекурсивное дерево может достичь гигантских размеров — одно и то же значение может вычисляться миллионы раз.

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

Ассоциативный массив — это абстрактный тип данных, в котором хранятся пары . Он поддерживается многими языками программирования и, как правило, реализуется как хеш-таблица или дерево поиска.

К примеру, в C++ и Java ассоциативный массив называется картой («map»), а в Python — словарём («dictionary»). В реализации, приведённой ниже, ассоциативный массив используется для хранения логических значений для пар .

1MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i):
2    if (w,i) is not in pack:
3        if i=0 and w=0:
4            pack[(w,i)] = true
5        else if i=0 and w>0:
6            pack[(w,i)] = false
7        else if i>0 and w_[i-1]>w:
8            pack[(w,i)] = MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i−1)
9        else: 
10            pack[(w,i)] = MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i−1) OR MemoizedKnapsack([w[0],…,w[n−1]],pack,w−w[i−1],i−1)
11    return pack[(w,i)]

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

На практике же итерационное решение, как правило, быстрее, потому что в нём нет рекурсивных издержек и оно использует более простые структуры данных. Например, массив вместо хеш-таблицы.

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

В целом, если необходимо решить все возможные подзадачи, итерационный вариант обычно быстрее.

Что дальше

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

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

А пока вы не ушли дальше — закрепите материал на практике:

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

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Жадная стратегия не даёт оптимального решения в задаче о рюкзаке — нужно перебрать возможные комбинации.
• Решение строится через рекурсию с мемоизацией или итеративное заполнение таблицы достижимости.
• Итерационный подход обычно быстрее, но рекурсивный с мемоизацией может быть удобнее в реализации.
• Количество подзадач ограничено, поэтому решение работает за O(nW) — достаточно эффективно даже для больших входов.