Рюкзак: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==0-1 Рюкзак== В самой простой форме задача о рюкзаке формулируется так: Даны $n$ предметов с...»)
 
Строка 12: Строка 12:
 
         dp[i][j] = dp[i - 1][j];
 
         dp[i][j] = dp[i - 1][j];
 
         if (a[i] <= j) {
 
         if (a[i] <= j) {
             dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + c[i]);
+
             dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + 1);
 
         }
 
         }
 
     }
 
     }

Версия 14:24, 5 октября 2019

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] = max(dp[i][j], dp[i - 1][j - a[i]] + 1);
6         }
7     }
8 }

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

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


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

Пусть, теперь предметов каждого типа может быть несколько, то есть даны не только веса и стоимости, но и максимальные количества каждого из предметов $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             dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i] * cnt] + c[i] * cnt)
6         }
7     }
8 }

Такое решение работает за $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]$ больше.