Рюкзак

Материал из Algocode wiki
Версия от 12:04, 17 октября 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

0-1 Рюкзак

В самой простой форме задача о рюкзаке формулируется так:

Даны $n$ предметов с весами $a_1,\dots, a_n$. Определите, на какой максимальный вес можно набрать предметов в рюкзак вместимости $W$.

Для решения этой задачи воспользуемся динамическим программированием. Обозначим за $dp[i][j]$ состояние, когда мы рассмотрели первые $i$ предметов и набрали ими $j$ веса. $dp[i][j]=True$, если такая ситуация возможна, иначе $dp[i][j]=False$.

Для каждого состояния $dp[i][j]$, которое возможно получить, мы можем либо взять предмет номер $i$ и попробовать обновить ответ из состояния $dp[i - 1][j - a[i]]$, либо не брать его и обновить ответ из $dp[i - 1][j]$. Очевидно, что мы можем получить 0 веса, рассмотрев 0 предметов.

1 for (int i = 1; i <= n; i++) {
2     for (int j = 0; j <= W; j++) {
3         dp[i][j] = dp[i - 1][j];
4         if (a[i] <= j) {
5             dp[i][j] = (dp[i][j] | dp[i - 1][j - a[i]]);
6         }
7     }
8 }


Ответом на задачу будет максимальное $n$, такое что $dp[n][j]$ равно $True$. Такое решение работает за $O(nW)$.

Уменьшаем затраты памяти

Заметим, что на самом деле нам достаточно одномерно массива $dp[w]$, в котором мы будем хранить, можно ли набрать такой вес. Изначально там будут храниться нули, после чего мы будем по очереди добавлять предметы и пересчитывать значения массива, пытаясь набрать вес w, используя новый предмет, если конечно раньше мы не могли набрать вес w.

Работать такой алгоритм будет всё ещё за $O(nW)$, поскольку мы для каждого предмета пытаемся перебрать все веса и пробуем этот вес набрать, используя этот предмет.

Неасимптотически уменьшаем затраты времени

Заметим, что нам нет необходимости каждый раз просматривать заново те веса, которые мы уже умеем набирать. Заведём изначально ещё дополнительный вектор $unreachable$ весов, которые мы не умеем набирать, изначально там все веса от $1$ до $W$ (нулевой вес мы всегда умеем набирать). На каждом шаге мы будем добавлять новый предмет и будем перебирать веса из $unreachable$, если его получилось набрать, то удаляем его из вектора: свапаем с последним элементом и делаем pop_back. Поскольку порядок весов в $unreachable$ нам неважен, мы можем спокойно переставлять элементы внутри него.

Рюкзак со стоимостями предметов

Теперь у каждого предмета есть стоимость $c_i$. Надо набрать не как можно больший вес, а как можно бОльшую суммарную стоимость предметов так, чтобы предметы по весу влезли в рюкзак.

Изменим значение $dp[i][j]$. Пусть оно равно максимальной стоиомости предметов, которые можно набрать среди первых $i$ с суммарным весом $j$. Порядок пересчета динамики остается прежним, но меняется обновление состояния: если мы не берем текущий предмет, то ответ не хуже, чем для первых $i-1$ предмета. А если берем, то места на предыдущие предметы остается $j - a[i]$, но мы прибавляем стоимость нового предмета к ответу.

1 dp[i][j] = dp[i - 1][j];
2 if (a[i] <= j) {
3     dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + c[i]);
4 }

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


Рюкзак с ограниченным числом предметов

Пусть, теперь предметов каждого типа может быть несколько, то есть даны не только веса и стоимости, но и максимальные количества каждого из предметов $k_1,\ldots,k_n$. Тогда для каждого состояния $dp[i][j]$ переберем, сколько мы взяли предметов такого типа и сделаем переход из каждого соответствующего состояния. Понятно, что мы не сможем взять более, чем $\lfloor\frac{W}{a_i}\rfloor$ предметов каждого типа.

 1 for (int i = 1; i <= n; i++) {
 2     for (int j = 0; j <= W; j++) {
 3         dp[i][j] = dp[i - 1][j];
 4         if (a[i] <= j) {
 5             for (int cnt = 0; cnt <= k[i]; cnt++) {
 6                 dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i] * cnt] + c[i] * cnt);
 7             }
 8         }
 9     }
10 }

Такое решение работает за $O(nW^2)$, так как $k_i$ могут быть очень большими, а $a_1=1$.

Можете попробовать решить эту задачу за $O(nW\log K)$, где $K$ — максимальное из $k_i$.

Рюкзак с неограниченным числом предметов

Пусть, теперь каждого предмета будет не $k_i$, а вообще бесконечно. Оказывается, задача стала только проще. Вернемся к обычному рюкзаку с весами и стоимостями. Единственное отличие будет в том, что теперь мы можем делать второй переход не из предыдущей строки, а прямо из текущей. При этом заметим, что для каждого состояния достаточно рассмотреть взятие только одного предмета данного типа, поскольку взятие двух и более будет рассмотрено одновременно.

1 for (int i = 1; i <= n; i++) {
2     for (int j = 0; j <= W; j++) {
3         dp[i][j] = dp[i - 1][j];
4         if (a[i] <= j) {
5             dp[i][j] = max(dp[i][j], dp[i][j - a[i]] + c[i]);
6         }
7     }
8 }

Такое решение работает за $O(nW)$.

Если $W$ велико, а $a_i$ достаточно малы, можно построить решение за $O(n + A^3)$, где $A$ — максимальное из $a_i$. Заметим, что если $W$ достаточно большое, то большая часть рюкзака будет занята предметами одного и того же типа с максимальной удельной стоимостью. Можно доказать, что одним и тем же предметом будет занято не менее $W-A^2$ веса. Таким образом, можно за $O(n)$ выбрать предмет с максимальным удельным весом, а для оставшихся предметов запустить предыдущий алгоритм, который сработает за $O(A^3)$, так как имеет смысл рассматривать не более $A$ предметов, а максимальный вес $A^2$.

Восстановление ответа

Во всех рассмотренных задачах восстановление ответа делается стандартным образом: нужно из ответа пройтись обратно до начала.

  • первый способ - это построить массив prev, где для каждой ячейки $dp[i][j]$ хранить, берем мы предмет i, или не берем предмет $i$.
  • второй способ - это определять это на ходу, смотря, какое из значений $dp[i - 1][j]$ или $dp[i - 1][j - a[i]] + c[i]$ больше.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin


Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex