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

вычисление идет от малых подзадач к большим,
ответы подзадач запоминаются в

таблице и используются при
решении больших задач.

Необходимо определить исходные данные задачи – параметры.

Например, при нахождении суммы некоторого набора чисел
параметрами задачи будут количество чисел и их значения.

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

параметров или с тем же числом параметров, но
при этом хотя

бы один из параметров имеет меньшее значение.

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

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

оптимальное
решение, при котором значение какого-то параметра будет
мин. или макс. в

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

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

≠ 0: s=1 +1/x+ 1/x2+ 1/x3+…+ 1/xn.

Подзадача: вычислим

сумму заданного ряда с параметром n=1.
Введем переменную a, в которую запишем значение 1/x, а
сумму ряда запишем в s. Далее решим подзадачу с параметром
n=2, используя значение, записанное в s: s= s + a/x. Затем решим
подзадачу с параметром n=3 и т.д.
s = 1, a = 1,
a = a/x,
s = s + a.

.
Определить cуществует ли набор предметов, суммарная масса которого
равна W

килограмм. Если такой набор существует, то определить
список предметов в наборе.

Обозначим через T(n, W) функцию, значение которой равно 1, если
искомый набор имеется, и равно 0, если набора нет. Аргументами
функции будут количество предметов n, по которому можно
определить вес каждого предмета, и суммарный вес набора W.

Определим подзазачи, решением которых будут функции T(i, j), где i
обозначает количество начальных предметов, j – требуемый
суммарный вес, где 0 ≤ i ≤ n, 1 ≤ j ≤ W.
Определим начальные значения функции T:
T(0, j) = 0 при j ≥ 1 (нельзя без предметов набрать массу j > 0),
T(i, 0) = 1 при i ≥ 1 (всегда можно набрать вес, равный 0).

i-ый предмет в набор не берется. Решение задачи с I

предметами
сводится к решению задачи с i – 1 предметом: T(i, j) = T(i - 1, j).
2) i-ый предмет в набор берется. Масса оставшихся предметов
уменьшается на величину wi: T(i, j) = T(i -1, j - wi).

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

Для оптимального решения из двух возможных вариантов нужно
выбрать наилучший. Рекурентное соотношение при i ≥ 1 и j ≥ 1:

T(i, j)= T(i -1, j) при j < wi
T(i, j)= max (T(i -1, j), T(i -1, j - wi)) при j ≥ wi.

= 3; w4 = 7; w5 = 6.

Решение нашего примера

определяется T[5, 16] = 1.
T[5, 16] = T[4, 16], то 5-ый предмет можно в набор не включать.
T[4, 16] ≠ T[3, 16] –> 4-ый предмет включается. Оставшаяся масса равна
16-w4 = 16-7 = 9.
T[3, 9] =T[2, 9] –> 3-ый предмет в набор не включаем.
T[2, 9] ≠ T[1, 9] ] –> 2-oй предмет включается. Оставшаяся масса равна
9-w2 = 9 - 5 = 4.
T[1, 4] ≠ T[0, 4] –> 1-oй предмет включается, оставшаяся масса равна 0.

выборку из n предметов, подлежащих упаковке в рюкзак,
имеющий ограничение по

весу, равное W килограмм.
При этом i-ый предмет характеризуется стоимостью сi  и весом
wi.
Итак, необходимо выбрать из этих предметов такой набор,
чтобы суммарная масса не превосходила заданной величины
W, а суммарная стоимость была максимальна.
Если перебирать всевозможные подмножества данного набора
из n предметов, то получится решение сложности не менее чем
O(2n).
В настоящее время неизвестен алгоритм решения этой задачи,
сложность которого является полиномиальной. Мы рассмотрим
алгоритм решения данной задачи для случая, когда все входные
данные – целые числа. Его быстродействие есть O(nW).

задачи. Аргументами функции является количество
предметов n, по которому можно определить

стоимость и массу
каждого предмета, и ограничение по весу W.

Определим подзазачи, решением которых будут функции T(i, j),
а именно, определим максимальную стоимость предметов, которые
можно уложить в рюкзак с ограничением по весу j килограмм, если
можно использовать только первые i предметов из заданных,
где 0 ≤ i ≤ n, 0 ≤ j ≤ n.
Определим начальные значения функции T : T(0, 0) = 0,
T(0, j) = 0 при j ≥ 1 (нет предметов, максимальная стоимость равна 0),
T(i, 0) = 0 при i ≥ 1 (можно брать любые из первых i предметов, но
ограничение по весу равно 0).

1) i-ый предмет не упаковывается в рюкзак. Решение задачи с
i

предметами сводится к решению задачи с i – 1 предметом:
T(i, j) = T(i - 1, j).
2) i-ый предмет упаковывается в рюкзак. Масса оставшихся
предметов уменьшается на величину wi, а при добавлении i-го
предмета стоимость выборки увеличивается на ci:
T(i, j) = T(i -1, j - wi) + ci.

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

выбрать наилучший.
Рекурентное соотношение при i ≥ 1 и j

≥ 1:

T(i, j)= T(i -1, j) при j < wi
T(i, j)= max (T(i -1, j), T(i -1, j - wi) + ci) при j ≥ wi.

= 7,
w2 = 5;
c3 = 4,
w3 =

3;
c4 = 9,
w4 = 7;
c5 = 8,
w5 = 6.

Решение примера определяется T[5, 16] = 21.
В примере суммарная масса предметов, подлежащих упаковке
в рюкзак, совпадает с W, в общем-же случае она не должна превосходить величину W.

значение T[n, W] со значением T[n-1, W].
1) Если T[n,

W] ≠ T[n-1, W], то предмет c номером n обязательно
упаковывается в рюкзак, после чего переходим к сравнению
элементов T[n-1, W - wn] и T[n-2, W- wn] и т.д.
2) Если T[n-1, W] = T[n-1, W], то n-ый предмет можно не
упаковывать в рюкзак. В этом случае следует перейти к
рассмотрению элементов T[n-1, W] и T[n-2, W] .

в рюкзак
не упаковывается. Переходим к сравнению элементов
таблицы T[4, 16] и

T[3, 16]. Их значения не равны, следовательно,
четвертый предмет должен быть включен в искомый набор, а
ограничение на вес становится равным 16 – w4= 16 – 7 =9.
Далее сравним элементы T[3, 9] и T[2, 9], они равны, поэтому
третий предмет в рюкзак не упаковывается и сравниваем T[2, 9] и
T[1, 9], они не совпадают, следовательно, второй предмет должен
быть взят в рюкзак, а ограничение на вес становится равным 9 - w2
= 9 – 5 =4.
И наконец сравниваем элементы T[1, 4] и T[0, 4], они не равны,
поэтому второй предмет включатся в искомый набор, при этом,
ограничение по весу становится равным 0.
Итак, для нашего примера в рюкзак упакуются предметы с
номерами 1, 2, 4.

//максимальный рюкзак для параметров
return;

//имеет нулевую ценность
else if (T[i-1][j] == T[i][j])
Print_item (i-1,j); //можно составить // рюкзак без i-го предмета
else {
Print_item(i-1,j-w[i]); //Предмет i //упаковывается в рюкзак
Printf(“%d “, i); // печать i-го предмета
}
}
В программе нужно вызвать функцию Print_item с параметрами (n,W).

Заметим, что рассуждения были приведены для случая, когда все предметы
различны. Cамостоятельно рассмотрите, какие изменения будут внесены в
таблицу в противном случае.

минимальное
число допустимых операций преобразовать строку S1 в строку
S2. Допустимой операцией

являются следующие операции
удаления символа из строки и вставки символа в строку:
DEL(S, i) – удалить i-ый элемент строки S;
INS(S, i, c) – вставить символ c после i-го элемента строки S.

Обозначим через S [i..j] – подстроку от i-го символа до j-го.

Пусть M(i,j) – минимальное количество операций, которые
требуются, чтобы преобразовать начальные i символов строки
S1 в начальные j символов строки S2: S1[0..i] –> S2[0..j].
S1[0..0] и S2[0..0] – пустые строки.

j операций вставки, т.е. M (0, j) = j .

Аналогично для преобразования строки длины i в пустую строку
требуется i операций удаления, т.е. M (i, 0) = i.

Пусть мы решили подзадачу c параметрами i –1 и j – 1. Это
означает, что из строки S1[0..i–1] построена строка S2[0..j–1] за
минимальное число допустимых операций M(i –1, j –1).

I) Пусть S1[i] = S2[j]. Тогда для получения строки S2[0..j] из
строки S1[0..i] не требуется никаких дополнительных операций.
Следовательно, M (i, j) = M (i – 1, j – 1).

1. Пусть из строки S1[0..i–1] построена строка S2[0..j] за
минимальное количество

операций M (i–1, j ). Тогда для
получения строки S2[0..j] из строки S1[0..i] требуется удалить
i-ый символ из строки S1.
2. Пусть из строки S1[0..i] построена строка S2[0..j–1] за
минимальное количество операций M (i, j–1). Тогда для
получения строки S2[0..j] из строки S1[0..i] потребуется одна
операция вставки i-го символа строки S1 после символа S2[j–1].

Из 2-х возможностей нужно выбрать лучшую.
Получим следующие рекуррентные соотношения:

(i, j) = min (M (i – 1, j –

1), M (i – 1, j ) + 1, M (i , j – 1) +1),
если S1[i] = S2[j];
M (i, j) = min (M (i – 1, j ), M (i , j – 1)) + 1,
если S1[i] ≠ S2[j];

Решением задачи будет значение M(m,n),
где m — длина строки S1, а n — длина строки S2.

строк и столбцов которой начинается с нуля
и элементами которой

будут числа, равные значениям функции, описанной
выше.

-1 0 1 2 3

получить строку
“aab”, используя две допустимых операции. В примере за три
допустимых

операции можно преобразовать строку S1 в S2.
Для определения операций нужно встать на последний символ
строки S1 и начать движение по таблице от правого верхнего
угла. В примере движение начнется с ячейки М[3,6].

Находясь в ячейке М[i, j], будем рассматривать два случая.
1) Если М[-1, i] = М[j, -1], то будем сдвигаться по диагонали влево-вниз,
попадая в ячейку М[i-1, j-1]. При этом будем перемещаться по строке S1 на
один символ влево, т.е. сделаем текущим в строке символ, находящийся в i-1
позиции.
2) Если М[-1, i] ≠ М[j, -1], то будем сдвигаться по таблице на одну позицию
либо влево, попадая в ячейку М[i, j-1], либо вниз в ячейку М[i-1, j]. Этот
выбор будет зависеть от того, какой из элементов, находящихся в этих
ячейках, меньше. При движении влево будем удалять i-ый символ в строке
S1, перемещась на один символ влево. При движении вниз будем вставлять
после i-го символа в строке S1 символ S2[j].

символ –
символ c. Так как М[-1, 3] = М[6,

-1], то осуществляем переход
в ячейку М[5, 2] и текущим в S1 становится предпослений
символ – b. Далее, так как М[-1, 2] ≠ М[5, -1], передвигаемся в
ячейку М[4, 2]. При этом вставим после текущего символа b
символ S2 [5] = d (j=5). Продолжая этот процесс вставим символ
S2 [4] = d, затем в строке S1 сделаем текущим сивол a, вставим в
строку S1 символ a. Процесс продолжается до тех пор, пока не
достигнем ячейки M[0,0].
Для нашего примера последовательность операций будет
следующая:
INS(S1, 2, ‘d’), INS(S1, 2, ‘d’), INS(S1, 1, ‘a’).
abc –> abc –> abdc –> abddc –> abddc –> aabddc

таблице представлено ниже.

школьных тренировках)
Если вы обратили внимание, то клавиатура
многих телефонов выглядит как

показано –>
Использование изображенных на клавишах
букв позволяет представить номер телефона
в виде легко запоминающихся слов. Многие
фирмы пользуются этим и стараются
подобрать себе номер телефона так, чтобы он содержал как можно больше
букв из имени фирмы.
Напишите программу, которая преобразует исходный цифровой номер телефона
в соответствующую последовательность букв и цифр, содержащую как можно
больше символов из названия фирмы. При этом буквы из названия фирмы
должны быть указаны в полученном номере в той же последовательности, в
которой они встречаются в названии фирмы. Например, если фирма называется
IBM, а исходный номер телефона — 246, то замена его на BIM не допустима,
тогда как замена его на 2IM или В4М является правильной.

S1= “IBM”, S2= “246”. При этом, если в S1 встречаются буквы, которые соответствуют
цифрам номера телефона в нужном порядке, то они останутся без изменения.

состоит только из заглавных букв латинского алфавита, количество которых не

превышает 80 символов. Вторая прока содержит номер телефона в виде последовательности цифр. Цифр в номере телефона также не более 80.
Формат выходных данных:
В единственной строке выходного файла должно содержаться число букв из измененного номера.
Пример файла входных данных:
IBM
246
Пример файла выходных данных:
2

= M1 x M2 x ... x Mn. (1)

Порядок, в

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

Умножение матрицы размера [р  q] на матрицу размера
[q r] требует pqr операций.

 М2  М3 

М4
[1020] [2050] [501] [1 100]
Если вычислять матрицу М в порядке: M1  ( М2  ( М3  М4,)), то
потребуется 125 000 операций.
(50*1*100)  [50 100], 5000; (20*50*100)  [20 100], 100000;
(10*20*100)  [10 100], 20000.

Вычисление же в порядке: ( M1  (М2  М3 )) М4 требует лишь
2 200 операций.
(20*50*1)  [20 1], 1000; (10*20*1)  [10 1], 200;
(10*1*100)  [10 100], 1000.

определим за какое минимальное количество
операций можно получить матрицу М из

равенства (1).
Будем считать подзадачами вычисление минимального
количества операций при перемножении меньшего, чем n,
количества матриц. В качестве параметров рассматриваемой
задачи возьмем индексы i и j (1 i  j  n), обозначающие
номера первой и последней матриц в цепочке
Mi  Мi+1  ...  Мj .
Сначала решим поздачи, когда j=i+1, т.е. когда перемножаются
две рядом стоящие матрицы. Решения – количество затраченных
операций, запишем в ячейке таблицы T с номерами (i. j).
Tij будет содержать число, равное количеству операций при
умножении цепочки матриц Mi  Мi+1, где 1 i  3.

T: t1,2, t2,3 и t3,4.
M1 

М2  М3  М4
[1020] [2050] [501] [1 100]

Далее перейдем к решению подзадач с параметрами j=i+2.
Рассмотрим, например, цепочку матриц M1 М2 М3.
Решением этой подзадачи будет минимальное количество операций,
выбранное из двух возможных порядков перемножения матриц:
(M1 М2) М3 и M1 (М2 М3). При этом для выражений в скобках
ответы уже записаны в таблице T. Результат запишем в ячейку T1,3.
Затем перейдем к решению подзадач с параметрами j=i+3 и т.д.

Мi+1  ...  Мj , где 1 i 

j  n. Ее можно
получить следующим образом:

Здесь tik — минимальная сложность вычисления цепочки
М' = Mi  Мi+1  ...  Мk ,
a tk+1,j — минимальная сложность вычисления цепочки
М˝= Mk+1  Мk+2  ...  Мj.
Третье слагаемое rikj равно сложности умножения М' на М˝. Утверждается, что tij ( j > i) — наименьшая из сумм этих трех членов по всем возможным значениям k, лежащим между i и j - 1.

начинается с вычисления tii для всех i, затем
ti,i+1 для всех

i, потом ti,i+2 и т. д. При этом tik и tk+1,j будут уже
вычислены, когда мы приступим к вычислению tij.
Оценка сложности данного алгоритма есть О (п3).
В результате работы алгоритма для примера из четырех матриц
будет построена следующая таблица T:
Порядок, в котором можно произвести эти умножения, легко определить,
приписав каждой клетке то значение k, на котором достигается минимум.

l++)
for (i=0; i

= 0; k < j; k++)
mij = min(mi,k+ mk+1,j + ri-1*rk* rj)
}
ri-1 – количество строк в M’
rk – количество столбцов в M’
rj – количество столбцов в M˝

в строке скобки таким образом, чтобы
значение полученного выражения было максимальнвым.

если ребро (i, j)E
M[i, j] = +∞ , если ребро

(i, j)E
0, если i = j

Обозначим через d [i, j] матрицу кратчайших
путей между всеми вершинами.
Вершины занумеруем числами от 1 до n.

номером i в вершину с номером j с промежуточными вершинами

из множества {1, 2, …, k}.

M[i, j] , если k = 0,
dij(k) =
min(dij(k-1) , dik(k-1) + dkj(k-1) ), если k1

D(n) содержит искомое решение

for (i = 0; i

to n do
dij(k)  min(dij(k-1), dik(k-1) + dkj(k-1) );
return D(n);
}

в школьных тренировках)
Consider an arbitrary sequence of integers. One can

place + or –
operators between integers in the sequence, thus deriving different
arithmetical expressions that evaluate to different values.
Let us, for example, take the sequence: 17, 5, –21, 15.
There are eight possible expressions:
17+5+ – 21+15=16 17+5+–21–15=–14
17+5– –21+15=58 17+5– –21–15=28
17–5 + –21+15=6 17–5+–21–15=–24
17–5– –21+15=48 17–5– –21–15=18
We call the sequence of integers divisible by K if + or – operators can be placed
between integers in the sequence in such way that resulting value is divisible by K.
In the above example, the sequence is divisible by 7 (17+5+–21–15=–14) but is not
divisible by 5. You are to write a program that will determine divisibility of sequence
of integers.
The first line of the input file contains two integers, N and K (1 ≤ N ≤ 10000,
2 ≤ K ≤ 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer
is not greater than 10000 by its absolute value.

gangsters are going to a restaurant. The i-th gangster comes

at the time Ti
and has the prosperity Pi. The door of the restaurant has K+1 states of openness
expressed by the integers in the range [0, K]. The state of openness can change
by one in one unit of time; i.e. it either opens by one, closes by one or remains
the same. At the initial moment of time the door is closed (state 0). The i-th
gangster enters the restaurant only if the door is opened specially for him, i.e.
when the state of openness coincides with his stoutness Si. If at the moment of
time when the gangster comes to the restaurant the state of openness is not
equal to his stoutness, then the gangster goes away and never returns.
The restaurant works in the interval of time [0, T].
The goal is to gather the gangsters with the maximal total prosperity in the
restaurant by opening and closing the door appropriately.

The first line of the input file contains the values N, K, and T, separated by spaces.
(1≤N,K≤100 ). he second line of the input file contains the moments of time when
gangsters come to the restaurant T1, T2, ..., TN, separated by spaces. The third line of the
input file contains the values of the prosperity of gangsters P1, P2, ..., PN, separated by
spaces. The forth line of the input file contains the values of the stoutness of gangsters
S1, S2, ..., SN, separated by spaces. All values in the input file are integers.

2 3 4 5 1
P = 1 1 1 1

1 100

гангстеры

L

– состояние двери

mi,j = max { [mi-1,j-1, mi-1,j, mi-1,j+1] + fi }
где pi, если L = si
0

fi =