Реферат: Динамическое программирование (задача о загрузке)

Состояние на этапе j можно описать с помощью переменной z_j , которая выражает количество имеющихся к концу этапа j овец для распределения на этапах j+1, j+2, ..., n, или с помощью переменной x_j , которая выражает количество имеющихся к началу этапа j+1 овец, обусловленное принятыми на этапах 1,2,...,j решениями. Первое определение ориентировано на построение рекуррентного соотношения
для процедуры обратной прогонки, тогда как второе определение приводит к использованию алгоритма прямой прогонки.

Алгоритм обратной прогонки

Обозначим через f_i (z_i ) максимальную прибыль, получаемую на этапах j,j+1,…,n, при заданном z_j . Рекуррентное соотношение имеет следующий вид:

Заметим, что y_j и z_j - неотрицательные целые числа. Кроме того, у_j (количество овец, проданных в конце периода j) должно быть меньше или равно z_j . Верхней границей для значений z_j , является величина 2^j k (где k- исходный размер стада), которая соответствует отсутствию продажи.

Алгоритм прямой прогонки

Обозначим через g_j (x_j ) максимальную прибыль, получаемую на этапах 1,2,...,j при заданном x_j , (где x_j — размер стада к началу этапа J+1). Рекуррентное соотношение записывается в следующем виде:

- целое.

Сравнение двух формулировок показывает, что представление x_{j -1} через x_j создает более существенные препятствия для вычислений, чем представление z_{j +1} через z_j .

В замене x_{j -1} =(x_j +y_j )/2 подразумевается целочисленность правой части, тогда как на равенство z_{j +1} =2(z_j -y_j ) такое требование не накладывается. Таким образом в случае процедуры прямой прогонки значения y_j и x_j , связанные неравенством

Y_j <=2^j k -X_j ,

должны дополнительно удовлетворять условию целочисленности их полусуммы, связанному с видом зависимости х_{j -1} от x_j ,. Рассмотренный пример иллюстрирует трудности вычислительного характера, которые обычно возникают при использовании алгоритма прямой прогонки.

2.3 Решение задачи о загрузке

Контрольная работа содержит вопросы по N различным темам. Каждый вопрос типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi. Максимально время, которое может затратить студент на контрольную работу W. Требуется определить максимальное количество баллов (вес), которое может набрать студент за отведенное время W=30. Данные приведены в таблице: