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

F (a₁, a₂, …, a_m) = С(a₁) + С(a₂) +…+ С(a_m),

где С(a_i) – функция, определенная для всех a_i. Показатели такого вида называют аддитивными. Требуется найти такой набор (a₁, a₂, …, a_m), чтобы стоимость была минимальной (максимальной).

Рассмотрим примеры многошаговых операций.

1. Руководитель предприятия намерен эксплуатировать некоторый аппарат в течение m лет. В начале каждого года он может принять одно из трех решений:

1. продать аппарат и заменить его новым;

2. провести капитальный ремонт и продолжить эксплуатацию;

3. продолжить эксплуатацию без капитального ремонта.

Требуется спланировать управление на все m лет, чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых аппаратов были минимальными. Управление состоит в выборе одного из трех решений в начале каждого года. Обозначим их цифрами 1, 2 и 3.

Стоимость складывается из годовых затрат. Решение представляет из себя комбинацию чисел 1, 2 и 3. Например, (3, 3, 2, 2, 2, 1, 3, …) означает: первые 2 года эксплуатировать аппарат без ремонта, последующие 3 года производить ремонт, в начале шестого года продать, купив новый, затем снова эксплуатировать без ремонта и т. д.

2. Планируется деятельность промышленных предприятий B₁, B₂, …, B_k на m лет. В начале периода на развитие всей группы предприятий выделены средства в размере S единиц. В процессе работы предприятия вложенные в него средства частично расходуются, а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств нужно выделять каждому предприятию, чтобы суммарный доход за m лет был максимальным ?

Суммарный доход представляет собой сумму доходов на отдельных шагах (годах). На каждом i-ом шаге предприятиям выделяются некоторые средства a_i1, a_i2, …, a_ik (первый индекс – номер шага, второй – номер предприятия), то есть a_i = (a _i1, a _i2, …, a _ik). Таким образом, элементы a_i представляют собой вектора.

В динамическом программировании элемент a_i на каждом шаге выбирается с учетом последствий в будущем на следующих шагах, то есть так, чтобы была минимальна сумма стоимостей на всех оставшихся до конца шагах плюс стоимость на данном шаге.

Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться отдельно, без планов на будущее. Это, очевидно, последний шаг. Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, m-й шаг. Но как его планировать, если неизвестно, чем кончился предпоследний?

Планируя последний шаг, нужно рассмотреть все возможности того, чем кончился предпоследний (m-1)-й шаг, и для каждой такой возможности найти наилучший вариант последнего шага. В динамическом программировании это называют условным оптимальным управлением, так как оно выбирается из условия, что предпоследний шаг закончился определенным образом. Затем находят условное оптимальное управление на (m-2)-м шаге и т. д., пока не доходят до первого шага, на котором находится уже истинное оптимальное управление, минимизирующее функцию стоимости. Сейчас двигаясь от начала к концу, на каждом i-ом шаге находят наилучшие значения a_i.

Таким образом, многошаговый процесс проходится дважды: первый раз от конца к началу, в результате чего находятся условные оптимальные управления и соответствующие условные оптимальные значения за оставшийся "хвост” процесса, а второй раз от начала к концу, когда остается "вспомнить” уже готовые рекомендации и найти оптимальные значения элементов a_i. Первый этап несравненно сложнее и длительнее второго, который почти не требует дополнительных вычислений.

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

Пусть, например, прямоугольник (квадрат) заполнен следующим образом:

	A	B	C	D	E
1	25	21	-10	14	9
2	-15	18	4	12	-1
3	10	14	7	8	14
4	6	6	3	18	-11
5	8	2	6	9	8

Начнем с конечной клетки E1. В нее можно попасть за один ход из клеток D1 и E2. В обеих клетках возможен единственный ход. В клетке D1 проставляется стоимость 14+9=23, а в e2 – (-1)+9=8. Далее проставим минимальную стоимость во все клетки первой строки, двигаясь влево от клетки D1. Для каждой такой клетки также имеется единственный ход, и стоимость формируется путем сложения стоимости текущей клетки с минимальной стоимостью клетки справа, рассмотренной на предыдущем шаге. Аналогично сверху вниз находятся минимальные стоимости для всех клеток последней вертикали E.

	A	B	C	D	E
1	59 ►	34 ►	13 ►	23 ►	9
2	20 ►	35 ►	▲ 17	20 ►	▲ 8
3	▲ 30	38 ►	▲ 24	▲ 28	▲ 22
4	▲ 36	33 ►	▲ 27	29 ►	▲ 11
5	43 ►	▲ 35 ►	▲ 33	28 ►	▲ 19

Начальная клетка A5 будет рассмотрена последней. Получим, что минимальная стоимость пути из A5 в E1 составляет 43 единицы. Сам путь восстанавливается по тем лучшим ходам, которые были сохранены. В этом примере есть 2 пути минимальной стоимости: A5, B5, B4, C4, C3, C2, C1, В1, E1 и A5, B5, C5, C4, C3, C2, C1, D1, E1.

Сформулируем общий принцип, лежащий в основе решения задач динамического программирования, называемый принципом оптимальности. Каково бы ни было состояние процесса перед очередным шагом, надо выбирать управление на этом шаге так, чтобы стоимость на данном шаге плюс оптимальная стоимость на всех последующих шагах была минимальной.

Отметим в заключение некоторые дополнительные аспекты применения методов динамического программирования.

1. Число шагов процесса может быть переменным. Например, это произойдет в рассмотренной задаче, если разрешить ход в соседнюю клетку по диагонали снизу вверх.

2. Функция стоимости может выражаться не суммой, а произведением стоимостей на отдельных шагах.

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

4. Задача может не иметь выраженного многошагового характера, но, тем не менее, сводится к подобным задачам. Например, при проектировании дороги можно разбить предполагаемую область прохождения дороги на маленькие участки и оценивать их в зависимости от разных условий (рельеф местности, болота, реки, лесные участки, тип грунта и т. п.).

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

Рассмотрим еще одну задачу, связанную с подходами динамического программирования [2].

Возрастающая подпоследовательность. Даны N целых чисел X₁, X₂, ..., X_N. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Ввод из файла INPUT.TXT. В первой строке находится число N. В следующей строке - N чисел через пробел.

Вывод в файл OUTPUT.TXT. В первой строке выводится количество невычеркнутых чисел, во второй - сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.

Ограничения: 1 ≤ N ≤ 5000, 1 ≤ X_i ≤ 60 000, время 2 с.

Пример

Ввод

6

2 5 3 4 6 1

Вывод

4

2 3 4 6

Во втором массиве для каждого элемента будем сохранять индекс следующего элемента в максимальной подпоследовательности, начинающейся от этого элемента.

Пусть I – номер текущего элемента, и оба массива заполнены для индексов с I+1 по N. В цикле по J будем перебирать все элементы от I+1-го до последнего. Если окажется, что X_I £ X_J, то элемент X_I может дополнить подпоследовательность, начинающуюся с элемента X_J. Найдем номер J, для которого длина C_J такой подпоследовательности максимальна. Положим C_I = C_J +1 и D_I = J. Сохраним номер, начиная с которого максимальная возрастающая подпоследовательность оказалась самой длинной.

На втором проходе уже в прямом направлении по массиву D, начиная с найденного номера, восстановим искомую подпоследовательность.

Рассмотрим, например, при N=6 последовательность 6, 3, 9, 4, 7, 5. Для нее

1. C₆ = 1, D₆ = 0 – признак отсутствия больших элементов ;

2. C₅ = 1, D₅ = 0 ;

3. C₄ = Max(C₅, C₆) + 1 =2, D₄ = 5 (подходит и D₄ = 6);

4. C₃ = 1, D₃ = 0 ;

5. C₂ = Max(C₂, C₃, C₄, C₅, C₆) + 1 =3, D₂ = 4 ;

6. C₁ = Max( C₃, C₅) =2, D₁= 3 .

Максимальное значение C_I достигнуто при I = 2. Одна из максимальных возрастающих подпоследовательностей 3, 4, 7 находится с помощью сохраненных в массиве D индексов 4 и 5.

Ниже приводится текст программы.

Program Posledov;

Const

R=5000; {максимальный размер последовательности}

Var

N: integer; {заданный размер последовательности}

X: array[1..R] of word;

C: array[1..R] of integer;

{C[i] - длина наибольшей возрастающей последовательности,

начинающейся с X[i]. Если подпосл. только из X[i], то 1}

D: array[1..R] of integer;

{D[i] - номер j - следующего числа X[j] в наибольшей

возрастающей подпоследовательности, начинающейся с X[i].

Если подпоследовательность только из X[i], то 0}

i,j,k,Max,IndMax: integer;

Fin,Fout: text;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,N);

For i:=1 to N do Read(Fin,X[i]);

Close(Fin);

C[N]:=1; {длина подпосл., начинающейся с последнего элемента}

Max:=1; {наибольшая длина среди всех подпоследовательностей}

IndMax:=1; {начальный индекс наибольшей подпоследовательности}

For i:=N-1 downto 1 do

begin

C[i]:=1; D[i]:=0;

{если от X[i] подпоследовательность не найдется}

For j:=i+1 to N do

if (X[i]<X[j]) and (C[j]>=C[i]) then

{ C[j]>=C[i] с учетом добавления X[i] }

begin

C[i]:=C[j]+1; {к подпоследовательности добавляется X[i]}

D[i]:=j;

if C[i]>Max then

begin

Max:=C[i];

IndMax:=i;

end

end

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

k:=IndMax;

WriteLn(Fout,C[k]);

Repeat

Write(Fout,X[k],' ');

k:=D[k];

Until k=0;

Close(Fout)

End.

Свинья-копилка. Для того чтобы начать свой бизнес, юный коммерсант решил накопить немного денег. С этой целью он отыскал свинью-копилку и начал собирать деньги. Требуется написать программу, которая определяла бы минимальную сумму денег, которая может находиться в копилке, зная её вес без монет, вес с монетами и вес монет каждого типа.

Ввод из файла INPUT.TXT . В первой строке содержатся два целых числа: E – вес пустой копилки (1 ≤ E ≤10000); F – вес копилки, заполненной монетами (1 ≤ E≤ F≤ 10000). Вторая строка содержит целое число N (1≤N≤500) — количество типов монет. Каждая из последующих N строк служит для описания монет заданных типов и содержит по два целых числа — P_i и W_i (1 ≤ P_i ≤ 30000, 1 ≤ W_i ≤ 10000, 1 ≤ i ≤ N), где P_i — достоинство монеты i-го типа, а W_i — ее вес.

Вывод в файл OUTPUT.TXT. В единственной строке выводится значение минимальной суммы денег, которая может находиться в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то выходной файл должен содержать No.

Пример

Ввод

10 110

2

1 1

30 50

Вывод

60

Program Kopilka;

Var

N,E,F,L: integer;

{число видов, вес пустой копилки, вес копилки с монетами, вес нетто}

Nmax: integer;

P: array [1..500] of integer; {ценность монет}

W: array [1..500] of integer; {вес монет}

Fin,Fout: text;

i,M: integer;

Cmin: array [0..10000] of longint;

{минимальные суммы в зависимости от веса}

S: longint;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,E,F);

ReadLn(Fin,N);

For i:=1 to N do ReadLn(Fin,P[i],W[i]);

Close(Fin);

L:=F-E; {чистый вес монет}

Cmin[0]:=0; {сумма денег пустой шкатулки}

For i:=1 to L do Cmin[i]:=-1;

{инициализация: вес недостижим}

For M:=1 to L do {M - общий вес монет}

begin

S:=MaxLongInt; {для поиска MIN ценности монет}

For i:=1 to N do

if (M>=W[i]) and (Cmin[M-W[i]]<>-1) then

{i-я монета может быть последней в наборе}

if Cmin[M-W[i]]+P[i]<S then S:=Cmin[M-W[i]]+P[i];

{сумма минимальна с учетом последней монеты}

if S< MaxLongInt then Cmin[M]:=S;

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

if Cmin[L]=-1 then WriteLn(Fout,'No')

else WriteLn(Fout,Cmin[L]);

Close(Fout)

End.