8.6. Задача о рюкзаке
Авторы: Алексей Толстиков, Александр Куликов
В этой статье вы разберёте одну из самых известных задач на динамическое программирование — задачу о рюкзаке. Вы узнаете, почему жадная стратегия здесь не срабатывает, и научитесь формулировать рекуррентные зависимости, чтобы находить оптимальное решение. Также вы сравните итерационный и рекурсивный подходы с мемоизацией и поймёте, в чём их плюсы и минусы.
Ключевые вопросы статьи
- Почему жадный алгоритм не подходит для задачи о рюкзаке?
- Как с помощью рекурсии и мемоизации находить решение без перебора всех подмножеств?
- В чём разница между рекурсивной и итерационной реализациями алгоритма?
Условие
Вы нашли несколько золотых слитков. Ваша цель — положить как можно больше золота в рюкзак вместимостью фунтов. Каждый слиток существует только в одном экземпляре. При этом можно либо взять слиток целиком, либо не брать его вовсе. И хотя все слитки на рисунке выше выглядят одинаково, они обладают разным весом — он приведён ниже.
Естественная жадная стратегия — взять самый тяжелый слиток, на который хватает вместимости рюкзака, и повторно проверить, а осталось ли место на ещё один слиток.
При наборе слитков, приведённом выше, и рюкзаке вместимостью «жадный» алгоритм выбирает слитки весом и . Однако оптимальное решение — использовать слитки весом 4, 6 и 10!
- Входные данные: Первая строка ввода содержит целое число (вместимость рюкзака) и количество золотых слитков . В следующей строке приведены целых чисел , которые определяют вес золотых слитков.
- Выходные данные: Максимальный вес золотых слитков, который можно уместить в рюкзак вместимостью .
- Ограничения: ; ; .
Пример 1
|
Ввод |
Вывод |
|
10 3 |
9 |
Сумма веса первого и последнего слитков равна .
Вместо решения изначальной задачи проверим, можно ли выбрать поднабор слитков с общим весом , если имеем слитков весом (мы перешли на отсчёт с нуля)?
Упражнение
Продемонстрируйте, как можно использовать это решение для выполнения задачи «Максимальное количество золота».
Первый вариант решения
Предположим, что заполнить рюкзак до конца действительно возможно: существует набор с общим весом . Включает ли он в себя последний слиток с весом ?
- Случай 1: Если , тогда рюкзак вместимостью может быть заполнен первыми слитками.
- Случай 2: Если , тогда мы можем убрать слиток с весом из рюкзака, и вес оставшихся слитков составит . Таким образом, рюкзак с вместимостью можно полностью заполнить первыми слитками.
В обоих случаях мы свели задачу к практически такой же, но с меньшим количеством слитков и меньшей вместимостью рюкзака. Так, переменная будет иметь значение , если существует возможность заполнить рюкзак с вместимостью первыми слитками, и значение в остальных случаях. Анализ двух вышеприведённых случаев приводит нас к следующему рекуррентному соотношению для :
Обратите внимание, что при второе выражение не имеет смысла.
Кроме того, и для любого .
В целом
Так как значения варьируются между 0 и , а значения — между 0 и , мы имеем переменных. Так как зависит от , мы обрабатываем все переменные в возрастающем порядке . В приведённом ниже псевдокоде мы используем двумерный массив pack размера , а сохраняет значение . Время выполнения данного решения составляет .
Knapsack([w[0],…,w[n−1]],W):
pack = two-dimensional array of size (W+1)×(n+1)
initialize all elements of pack to false
pack[0][0] = true
for i from 1 to n:
for w from 0 to W:
if w[i-1] > w:
pack[w][i] = pack[w][i−1]
else:
pack[w][i]←pack[w][i−1] OR pack[w−w[i−1]][i−1]
return pack[W][n]
В приведённой ниже двумерной таблице представлены результаты вызова Knapsack([1,3,4], 8. F и T означают значения false и true.
Второй вариант решения
Другое решение будет заключаться в анализе поднаборов всех слитков. Наша цель — найти поднабор из слитков с общим весом .
Простой подход к такой задаче — просматривать все поднаборы и проверять, есть ли поднабор с весом . Так как каждый слиток можно или пропустить, или взять, каждый поднабор из трёх слитков, который мы анализируем (, , ), можно представить сине-красным бинарным вектором:
Теперь мы представим каждый поднабор слитков как путь, начинающийся от узла сетки .
- Если первый бит — синий, то он соответствует синему горизонтальному сегменту сетки, связывающему с .
- Если первый бит — красный, то он соответствует красному сегменту сетки, связывающему с .
- Обработав первые битов, мы получаем сине-красный путь от до некого узла на сетке.
- Если следующий бит — синий, мы связываем с .
- Если следующий бит — красный, мы связываем с , как показано ниже для вектора 101:
Рисунок ниже демонстрирует пути, которые соответствуют всем восьми бинарным векторам с длиной 3.
Теперь мы накладываем все эти восемь путей на одну сетку:
Мы классифицируем узел на сетке как истинный («true») при наличии пути от к на рисунке выше. В других случаях — ложный («false»). Теперь мы можем полностью заполнить рюкзак с вместимостью поднабором из первых слитков, если узел — истинный («true»). Узел будет истинным в случаях, если в него проходит или синее, или красное ребро. То есть, если или истинны. Это наблюдение приводит нас к предыдущему рекуррентному соотношению и к такому же решению с динамическим программированием.
Третий вариант решения
А вот ещё один вариант решения, который основан на мемоизации. Приведённый ниже псевдокод рекурсивно вычисляет рекуррентное соотношение из решения 1:
RecursiveKnapsack([w[0],…,w[n−1]],w,i):
if i=0 and w=0:
return true
else if i=0 and w>0:
return false
else if i>0 and w_[i-1]>w:
return RecursiveKnapsack([w[0],…,w[n−1]],w,i−1)
else:
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»). В реализации, приведённой ниже, ассоциативный массив используется для хранения логических значений для пар .
MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i):
if (w,i) is not in pack:
if i=0 and w=0:
pack[(w,i)] = true
else if i=0 and w>0:
pack[(w,i)] = false
else if i>0 and w_[i-1]>w:
pack[(w,i)] = MemoizedKnapsack([w[0],…,w[n−1]],pack,w,i−1)
else:
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)
return pack[(w,i)]
Время выполнения итогового решения составляет , так как количество рекурсивных вызовов, не являющихся уточняющими запросами в ассоциативный массив, не превышает это число. Следовательно, это такое же время выполнения, как и у соответствующего итерационного алгоритма.
На практике же итерационное решение, как правило, быстрее, потому что в нём нет рекурсивных издержек и оно использует более простые структуры данных. Например, массив вместо хеш-таблицы.
Тем не менее с рассматриваемой задачей ситуация иная: при некоторых наборах данных, рекурсивная версия быстрее итерационной. К примеру, если мы умножим все весовые значения на , то время выполнения итерационного алгоритма также умножится на , в то время как время выполнения рекурсивного останется таким же.
В целом, если необходимо решить все возможные подзадачи, итерационный вариант обычно быстрее.
Что дальше
Теперь вы умеете решать задачу о рюкзаке с помощью динамического программирования — как рекурсивно с мемоизацией, так и итерационно. Вы научились строить таблицу достижимости весов и поняли, почему простая жадность здесь не работает.
Далее — задача про сувениры: вы узнаете, как свести динамическую задачу к более простой, если ограничен не вес, а количество предметов и целевая сумма. Новый подход позволит взглянуть на подмножества и веса под другим углом.
Ключевые выводы статьи
- Жадная стратегия не даёт оптимального решения в задаче о рюкзаке — нужно перебрать возможные комбинации.
- Решение строится через рекурсию с мемоизацией или итеративное заполнение таблицы достижимости.
- Итерационный подход обычно быстрее, но рекурсивный с мемоизацией может быть удобнее в реализации.
- Количество подзадач ограничено, поэтому решение работает за O(nW) — достаточно эффективно даже для больших входов.