2.3. Реализации метода динамического программирования для задачи о рюкзаке.

Рассмотрим итерационную реализацию метода динамического программирования. Результаты расчетов вносятся в табл. 2.1.

Таблица 2.1.

s	i=n		…		i=1
	Un(s)	Wn(s)			U1(s)	W1(s)
0	0	0			0	0
…
s≥ai	1	Ci
…
b	1	Ci

Количество строк в таблице соответствуют возможным значениям остаточной грузоподъемности рюкзака (первый столбец). Здесь i- номер предмета для упаковки.

Для определения порядка добавления предметов используем «жадный» алгоритм.

Жадный алгоритм для задачи о рюкзаке состоит в следующем:

• вначале множество предметов Q упорядочивается по убыванию «удельной ценности» (или цены единицы веса) предметов, т.е. так, чтобы

≥ ≥ . . . ≥ ;

• затем, начиная с пустого множества, к приближенному решению Q (сначала оно пустое) последовательно прибавляются предметы из упорядоченного множества Q;

• при каждом очередном добавлении предмета в рюкзак выполняется проверка, не превосходит ли его вес величины оставшегося запаса объема рюкзака;

• окончание просмотра всех предметов завершает процесс построения приближенного решения задачи о рюкзаке.

Согласно алгоритму начинаем заполнять таблицу с последнего предмета, (т.е. идем в обратном порядке). Предмет будет помещен в рюкзак, если s≥a_i. Где i-номер предмета с максимальной удельной ценностью (i=n). Тогда U_i(s) =1 и W_i(s)= c_i.

Далее, чтобы вычислить значения U_i(s) и W_i(s) для, i=1, . . . , n-1 требует строить для каждой пары вспомогательные таблицы.

Табл. 2.2 демонстрирует вычисление величин U_n-1, W_n-1(s) для s_n-1 > a_n-1 по формуле (2.11). соответственно ищутся в отдельных таблицах оставшиеся величины U_i(s), W_i(s) по той же формуле.

Таблица 2.2

u	S -an-1u	Wn(S -an-1u)	cn-1u	cn-1u+ Wn(S -an-1u)
0
1

Где в таблице 2.2 u –допустимое управление; S-a_n-1u – остаточный вес рюкзака; W_n(S-a_n-1u) – выигрыш, равный стоимости предмета n, находящегося в рюкзаке с остаточным весом S-a_n-1u; c_n-1u – стоимость n-1 предмета зависимости от значения u; c_n-1u + W_n(S-a_n-1u) – выигрыш, равный суммарной стоимости предметов n и n-1, находящихся в рюкзаке с остаточным весом S-a_n-1u.

Значения U_n-1, W_n-1(s) определяются по строке с максимальным выигрышем в последней колонке, т.е. из двух значений c_n-1u+ W_n(S-a_n-1u) выбирается наибольшее (при условии W→max), и далее они заносятся в таблицу 2.1.

В результате метод динамического программирования дает следующее оптимальное управление процессом укладки: U^* = ( , . . . , ). [6]