WikiSort.ru - Программирование

Задача о неограниченном рюкзаке

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

Пусть вес каждого предмета ${\displaystyle w_{i}}$ является целым неотрицательным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех ${\displaystyle w\in \mathbb {Z} :0\leq w\leq W}$ , где ${\displaystyle W}$  — заданная грузоподъемность. Определим ${\displaystyle m[w]}$ как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью ${\displaystyle w}$ .

Для ${\displaystyle m[w]}$ можно записать рекуррентные формулы:

• ${\displaystyle m[0]=0}$
• ${\displaystyle m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])}$ ^[12],

где ${\displaystyle v_{i},w_{i}}$  — ценность и вес ${\displaystyle i}$ -го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения ${\displaystyle m[w]}$ , начиная с ${\displaystyle 0}$ и до ${\displaystyle W}$ ^[12]. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.

Так как на каждом шаге необходимо найти максимум из ${\displaystyle n}$ предметов, алгоритм имеет вычислительную сложность ${\displaystyle O(nW)}$ . Поскольку ${\displaystyle W}$ может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. Поэтому эффективность данного алгоритма определяется значением ${\displaystyle W}$ . Алгоритм даёт отличные результаты при ${\displaystyle W\leq 1000}$ , но не очень хорошие для ${\displaystyle W\geq 10\ 000\ 000}$ ^[13].

Задача о рюкзаке 0-1

Решение задачи о рюкзаке 0-1 близко к решению предыдущей задачи, но необходимо учесть тот факт, что каждый предмет имеется в единственном экземпляре. Пусть ${\displaystyle m[i,w]}$  — максимальная ценность предметов, полученных из первых ${\displaystyle i}$ имеющихся предметов, с суммарным весом не превышающим ${\displaystyle w}$ .

Рекуррентные соотношения:

• ${\displaystyle m[0,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$ , если ${\displaystyle w_{i}>w}$
• ${\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}$ , если ${\displaystyle w_{i}\leq w}$

Вычисляя ${\displaystyle m[n,W]}$ , можно найти точное решение. Если массив ${\displaystyle m[i,w]}$ помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных^[12].

 1 // Ввод:
 2 // Ценности предметов (загруженные в массив v)
 3 // Веса предметов (загруженные в массив w)
 4 // Количество предметов (n)
 5 // Грузоподъемность (W)
 6 
 7 for j from 0 to W do:
 8     m[0, j] := 0
 9 
10 for i from 1 to n do:
11     for j from 0 to W do:
12         if w[i] > j then:
13             m[i, j] := m[i-1, j]
14         else:
15             m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси ${\displaystyle X}$ откладывается количество предметов, по оси ${\displaystyle Y}$  — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось ${\displaystyle Y}$ равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета^[14].

Таким образом, любому решению задачи соответствует некоторый путь в построенном дереве. Задача сводится к нахождению пути максимальной длины^[14].

Пусть вместимость рюкзака ${\displaystyle W=14}$ .

Из рисунка видно, что суммарная ценность для оптимального решения равна 7, так как это максимальная ценность в построенном дереве.

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

Рекуррентные соотношения можно записывать не только относительно веса предметов, но также и относительно ценности. Для этого обозначим за ${\displaystyle y[i,V]}$ минимальный вес предметов, суммарной ценностью ${\displaystyle V}$ , который можно получить из первых ${\displaystyle i}$ предметов. Если необходимый вес получить невозможно, то отметим это как ${\displaystyle y[i,V]=W+1}$ .

После этого решим функциональное уравнение динамического программирования:

${\displaystyle y[i,V]={\begin{cases}y[i-1,V],&{\text{if }}V<v_{i}\\\min\{\ y[i-1,V],y[i-1,V-v_{i}]+w_{i}\},&{\text{if }}V\geq v_{i}\end{cases}}}$ ,

с начальными условиями:

${\displaystyle y[0,0]=0}$

${\displaystyle y[0,V]=W+1}$ ^[15]

Решение задачи о сумме подмножеств

Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть ${\displaystyle W}$  — грузоподъёмность рюкзака, ${\displaystyle w_{i}}$ — вес ${\displaystyle i}$ -го предмета, а его стоимость ${\displaystyle v_{i}=w_{i}}$ . Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

${\displaystyle W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}}$

Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор ${\displaystyle (x_{1},..,x_{n})}$ . В качестве функции приспособленности следует использовать близость суммарного веса предметов к ${\displaystyle W}$ , с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем ${\displaystyle W}$ )^[19].

Определим формально функцию приспособленности ${\displaystyle f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R} }$ . Пусть ${\displaystyle {\mathcal {S}}}$  — сумма весов всех предметов. Тогда ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$  — максимально возможное отклонение веса предметов в рюкзаке от ${\displaystyle W}$ .

Пусть ${\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}}$  — суммарный вес предметов для данного вектора. Тогда положим:

${\displaystyle f(x_{1},..,x_{n})={\begin{cases}1-{\sqrt {\frac {W-W'}{W}}},&W'\leq W,\\1-{\sqrt {\frac {W'-W}{\Delta _{max}}}},&W'>W.\end{cases}}}$ ^[19]

Пользуясь общим алгоритмом, можно найти приближенное решение:

1. Создать случайный набор особей — популяцию.
2. Подсчитать функцию приспособления для каждой особи.
3. Оставить только наиболее приспособленных особей (естественный отбор).
4. Произвести скрещивания особей.
5. Подвергнуть потомков мутации.
6. Продолжить со второго шага.

Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций^[19].