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

2016-12-07T14:32:26Z

94.25.228.117: /* Варианты решения */

'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.

== Формулировка задачи ==

Дано <tex>N</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:

#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.

== Варианты решения ==

Задачу о рюкзаке можно решить несколькими способами:

* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>

* Метод динамического программирования. Сложность — <tex>O(N \times W)</tex>.

== Метод динамического программирования ==

Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.

<tex>A(k, 0) = 0</tex>

<tex>A(0, s) = 0</tex>

Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:

#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex>
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>

То есть:
<tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>

Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.

'''Восстановим набор предметов, входящих в рюкзак'''

Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:

#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>

Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.

== Реализация ==
Сначала генерируем <tex>A</tex>.

for i = 0..W
A[0][i] = 0;
for i = 0..N
A[i][0] = 0; //Первые элементы приравниваем к 0
for k = 1..N
for s = 1..W //Перебираем для каждого k все вместимости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
else
A[k][s] = A[k-1][s]; //иначе, не кладем

Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:

findAns(k, s)
if A[k][s] == 0
return;
if A[k-1][s] == A[k][s]
findAns(k-1, s);
else
findAns(k-1, s - w[k]);
ans.push(k);

Сложность алгоритма <tex>O(N \times W)</tex>

== Пример ==

<tex>W = 13, N = 5</tex>

<tex>w_{1} = 3, p_{1} = 1 </tex>

<tex>w_{2} = 4, p_{2} = 6 </tex>

<tex>w_{3} = 5, p_{3} = 4 </tex>

<tex>w_{4} = 8, p_{4} = 7 </tex>

<tex>w_{5} = 9, p_{5} = 6 </tex>

[[Файл:Knapsack problem0.png]]

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.

Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.

Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.

'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''

Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.

[[Файл:Задача о рюкзаке3.png]]

Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.

Стоимость рюкзака <tex>= 6 + 7 = 13</tex>

Вес рюкзака <tex>= 4 + 8 = 12</tex>

=Другие задачи семейства=
==Ограниченный рюкзак ==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы

* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.
* Методом динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 1 до <tex>W</tex>, по рекуррентной формуле:

<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

=== Реализация ===
for i = 0..W // база
d[0][i] = 0;
for i = 1..N
for c = 1..W //Перебираем для каждого i, все вместимости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);

Сложность алгоритма <tex>O(NW^2)</tex>.

==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;

Сложность алгоритма <tex>O(NW)</tex>.

==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.

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

=== Реализация ===
sort(); // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
sum += p[i];
W -= w[i];
else
sum += W / w[i] * p[i];// иначе берем сколько можно и выходим
break;

==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - задача из семейства, в которой стоимость предмета совпадает с его весом.

'''Пример:''' Машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.

Часто задачу ставят как, дать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;

*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;

Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.

Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W</tex>.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

'''Пример:''' Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
===Формулировка Задачи===
Математически задачу можно представить так:

*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;

*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>;

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>.

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

==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>

так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.

<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

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

==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===

Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,

при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</tex>.

<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>.

<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.

= Литература =
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]

Викиконспекты - Вклад участника [ru]

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