Решение задачи о ранце с использованием рекуррентных соотношений динамического программирования

Решение задачи о ранце с использованием табличной схемы

Рассмотрим задачу о ранце

v(i) x(i) v(0), (1)

x(i) {0,1}, (2)

F(x) = c(i) x(i) max. (3)

Не уменьшая общности, будем предполагать, что все параметры задачи целые неотрицательные числа.

Обозначим через Z (k,p) - задачу (1) - (3), при условиях, что предметов k, k m, а вместимость ранца p, p v(0). Пусть R(k,p) - оптимум задачи Z(k,p). Тогда, очевидно, что оптимум исходной задачи (1) -(3) совпадает с оптимумом задачи Z(m,v(0)) и равен R(m,v(0)). Для определения величины R(m,v(0)) можно построить следующие рекуррентные соотношения:

R(k+1,p) = R(k,p), если v(k+1) > p, (4)

R(k+1, p) = max { R(k,p), c(k+1) + R(k, p- v(k+1))}, если p> v(k+1) + 1.

Рекуррентные соотношения (4), с учетом граничных условий

R(1,p) = 0, если с(1) > p, (5)

R(1,p) = c(1), если c(1) < p+1,

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

Замечание.

Результаты вычислений по рекуррентным соотношениям (4), (5) удобно представить в виде таблицы с m строками и v(0) столбцами (отсюда и название метода), в которой приводятся значения соответствующих величин R(k,p). Для того чтобы решить исходную задачу о ранце необходимо заполнить клетку таблицы с координатами: m - тая строки и столбец с номером v(0). Для этого не требуется заполнить все m v(0) клеток таблицы, а лишь те, которые используются для вычисления значений величины R(m,v(0)).

Рассмотрим задачу о ранце

v(i) x(i) v(0), (1)

x(i) {0,1}, (2)

F(x) = c(i) x(i) max. (3)

Пусть G={1,2,...,m} - множество номеров предметов.

Обозначим через W(G’, p) - суммарную полезность тех предметов, которые будут положены в ранец из предметов множества G’, при вместимости ранца p, и наилучшем способе выбора предметов (с точки зрения функционала задачи),

G’ G, p<v(0) + 1.

Обозначим через S = { i/ c(i) < p+1, i G’}.

Тогда

W(G’,p) = max [ c(i) + W(G’\{i}, p - v(i))], (4)

где максимум берется по предметам из множества S.

Рекуррентные соотношения (4), с учетом граничных условий:

W(G’,p) = 0, если S - пустое множество.

Дата добавления: 2017-02-01; Просмотров: 60; Нарушение авторских прав?; Мы поможем в написании вашей работы!