8.2.4. Приближения в задаче об упаковке рюкзака

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

На первом этапе список объектов должен быть отсортирован по удельной стоимости (отношение стоимости к объему).

В таблице 8.2 приведен пример списка объектов, каждый из которых задан парой (вес, стоимость), и соответствующий отсортированный список.

Табл. 8.2 Пример списка объектов

Исходный список	(25,50)	(20,80)	(20,50)	(15,45)	(30/105)	(35,35)	(20,10)	(10,45)
Удельная стоимость	2	4	2.5	3	3.5	1	0.5	4.5
Отсортированный список	(10,45)	(20,80)	(30/105)	(15,45)	(20,50)	(25,50)	(35,35)	(20,10)

На втором этапе начинается заполнение рюкзака последовательно идущими элементами отсортированного списка объектов. Если очередной объект не входит, то он отбрасывается, и происходит переход к следующему объекту. Эти действия повторяются до тех пор, пока рюкзак не будет заполнен или будет исчерпан список объектов.

Так, для списка, приведенного в таблице 8.2, при заданной емкости 80, в рюкзак будут помещены объекты (10,45), (20,80), (30,105), (15,45). Стоимость упаковки при этом – 275, заполненный объем – 75.

Это не оптимальное решение. Так, первые 3 элемента с добавкой пятого дадут объем 80 и стоимость – 280.

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

8.3. Вопросы для самопроверки

1. Определение классов Р, NP, NP–полных классов задач.

2. Примеры NP–полных задач.

3. Решить приближенно задачу коммивояжера для графа:

   Из\До	2	3	4	5	6	7
   1	5	1	2	16	17	21
   2		10	7	18	8	15
   3			9	11	13	4
   4				3	20	14
   5					12	6
   6						19

4. Эвристические алгоритмы раскладки по ящикам.

5. Приближения в задаче об упаковке рюкзака.

9. Динамическое программирование

Ричард Беллман ввел понятие динамического программирования для характеристики алгоритмов, действующих в зависимости от меняющейся ситуации [6]. Ряд иллюстративных примеров в классической книге Р. Беллмана и Р.Дрейфуса "Прикладные задачи динамического программирования" открывает задача оптимальной по стоимости одномерной упаковки рюкзака. Повышенный интерес к этой задаче, равно как и к ее многочисленным модификациям, связан как с разнообразными практическими областями применения, так и с отсутствием "быстрых" алгоритмов решения. Метод динамического программирования, хотя и позволил существенно сократить полный перебор вариантов, но реализующие этот метод алгоритмы не являются полиномиальными относительно длины входа.

Реализация метода динамического программирования, обеспечивающего точное решение задачи одномерной упаковки, может быть осуществлена следующими двумя принципиально разными алгоритмами:

– табличным алгоритмом, опирающимся на вычисление и хранение векторов оптимальной упаковки для всех последовательных целочисленных значений объема;

– рекурсивным алгоритмом, непосредственно реализующим основное функциональное уравнение Беллмана для задачи одномерной оптимальной упаковки.

Напомним общую постановку задачи одномерной оптимальной по стоимости упаковки.

Пусть задано множество типов грузов:

Y = { y_i }, , y_i ={ v_i , c_i }, i  {1,2,…,N},

где каждый элемент y_i обладает целочисленным линейным размером – v_i, или "объемом" в общепринятых терминах задач упаковки, и ценовой характеристикой – c_i, которая содержательно отражает практически значимые предпочтения для загрузки объектов данного типа.

Так же целочисленным значением задан основной объем упаковки V. В классической постановке элементы y_i называются типами грузов [6]. Для описания количества загружаемых в объем V элементов y_i вводится в рассмотрение следующий характеристический вектор:

X = {x_i}, x_i – неотрицательное целое, i  {1,2,…,N} (9.1)

Значение компонента вектора x_i = k соответствует загрузке k элементов типа y_i в объем V.

Среди всех возможных упаковок объема V грузами из Y должна существовать, по крайней мере, одна упаковка, максимизирующая суммарную стоимость в объеме V, что приводит к следующей постановке задачи:

Максимизировать линейную форму:

, (9.2)

при выполнении следующего условия:

(9.3)

Содержательно условие (9.3) означает, что суммарный объем, занимаемый грузами всех типов в количествах, указанных характеристическим вектором X, не должен превышать общего объема упаковки.

Один из вариантов точного решения задачи методом динамического программирования – это табличный алгоритм [6], позволяющий получить набор оптимальных решений не только для заданного объема V, но и для всех промежуточных дискретных значений этого объема.

Обозначим вектор оптимальной упаковки для объема v элементами y_j, y_i  {1,2,…,k}, через , а через f_k(v) – стоимость оптимальной упаковки в этом объеме. В силу принципа оптимальности , а порядок предъявления элементов y_j не является существенным.

Решение табличным алгоритмом осуществляется на основе функционального уравнения метода динамического программирования:

Результатом решения задачи является набор оптимальных значений целевой функции f_N (v) и соответствующих векторов оптимальной упаковки для всех объемов v от 0 до V исходными элементами (типами грузов) из Y. Табличный способ позволяет получить оптимальные решения для всех промежуточных объемов упаковки.

Пример формирования таблицы оптимальной упаковки для исходных данных оптимального дохода в табл. 9.1, представлен в табл. 9.2.

Табл. 9.1. Таблица исходных данных.

1	2	3
2	3	5
3	4	7

Табл. 9.2. Таблица оптимального дохода.

1	0	0		1	0	0	0		1	0	0	0	0
2	1	3		2	1	0	3		2	1	0	0	3
3	1	3		3	0	1	5		3	0	1	0	5
4	2	6		4	2	0	6		4	0	0	1	7
5	2	6		5	1	1	8		5	1	1	0	8
6	3	9		6	0	2	10		6	0	2	0	10
7	3	9		7	2	1	11		7	0	1	1	12
8	4	12		8	1	2	13		8	0	0	2	14
9	4	12		9	0	3	15		9	0	3	0	15
10	5	15		10	2	2	16		10	0	2	1	17

Ниже представлена реализация данного алгоритма:

инициализация начальных условий