Изменения

Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dotsldots, a_n \ (a_i \ge geqslant 0)</tex>. Требуется расставить знаки <tex dpi = "120">+, \times</tex> и скобки в последовательности, чтобы значение полученного арифметического выражения было максимальным.

Данная задача решается с использованием [[Динамическое_программирование | принципа оптимальности на подотрезках]]. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dotsldots, a_j</tex>.

* <tex>d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k] \times cdot d[k+1][j])] \ (i < j)</tex> <br />

Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <tex>i</tex>-го и заканчивая <tex>j</tex>-м. Запоминать результат оптимального решения соответствующей подзадачи мы будем в элементе <tex>d[i, j]</tex> матрицы, размером <tex>n\times n</tex>, диагональные элементы которой <tex>(d[i, i])</tex> равны операндам, а для <tex>i > j</tex> все элементы равны <tex>0</tex>. Пусть мы хотим подсчитать значение арифметического выражения для операндов, начиная с <tex>i</tex>-го и заканчивая <tex>j</tex>-м для <tex>i < j</tex>. Если мы предположим, что последней будет выполняться арифметическая операция, расположенная после операнда с номером <tex>k (k < j)</tex> и эта операция — сложение, то результат подсчета будет равен сумме элементов <tex>d[i, k]</tex> и <tex>d[k+1, j]</tex> нашей матрицы. С умножением ситуация несколько более сложная. Так как операндами могут быть и отрицательные числа, то для нахождения максимума из произведений нужно знать не только максимальные, но и минимальные значения для арифметических операций над операндами с <tex>i</tex>-го по <tex>k</tex>-й и с <tex>k+1</tex>-го по <tex>j</tex>-й соответственно. Значит для любой последовательности операндов нужно хранить значение как максимально, так и минимально возможного результата выполнения арифметических операций над ними. Однако, дополнительная матрица для хранения минимальных значений не нужна. Так как для <tex>i > j</tex> матрица <tex>d</tex> не заполнена, мы можем отвести эти элементы для хранения минимумов, только запоминать результат решения этой подзадачи для операндов, начиная с <tex>i</tex>-го и заканчивая <tex>j</tex>-м, мы будем в элементе <tex>d[j, i]</tex>. Тогда в общем случае, если после k-го операнда стоит операция умножения, то максимальный результат будет равен <tex>max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] \times cdot d[k+1][j]))</tex>;

<font color = "green">// d - матрица как в описании; a - заданная последовательность из n элементов; i, j, k - счётчики</font>

'''int maxValueOfExpression'''(a, n): '''for ''' i := 1 '''to ''' n do: d[i][i] := a[i];

'''for ''' i := n - 1 '''downto ''' 1 do: '''for ''' j := i + 1 '''to ''' n do: '''for ''' k := i '''to ''' j - 1 do: d[i][j] := max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] * d[k+1][j])); write( '''return''' d[1][n]); // вывод ответа 

|&nbsp;&nbsp;<tex>32</tex>&nbsp;&nbsp;

== Источники Восстановление ответа ==С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <tex>d</tex> хранить каким способом был получен оптимальный ответ. То есть будем хранить <tex>index</tex> {{---}} границу раздела на 2 подотрезка <tex>(i \ldots index</tex> и <tex>index + 1 \ldots j)</tex> и <tex>operation</tex> {{---}} операцию совершенную над двумя отрезками (<tex>+, \times</tex>). В итоге для каждого отрезка мы будем знать какой знак и куда поставить. Для простоты будем заключать каждый полученный подотрезок в скобки. Таким образом мы получим выражение, в котором полностью расставлены скобки. Для вышеприведенного примера таблица будет выглядеть так: :{| border = 1; class="wikitable"|-align = "center"|&nbsp;&nbsp;<tex>index</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 1</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 2</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 3</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 4</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 1</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>1</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>1</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 2</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>2</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>3</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 3</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>3</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 4</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>-</tex>&nbsp;&nbsp;|} :{| border = 1; class="wikitable"|-align = "center"|&nbsp;&nbsp;<tex>operation</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 1</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 2</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 3</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>j = 4</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 1</tex>&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;<tex>+</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>\times</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>\times</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 2</tex>&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;<tex>+</tex>&nbsp;&nbsp;|&nbsp;&nbsp;<tex>\times</tex>&nbsp;&nbsp;|-align = "center"|&nbsp;&nbsp;<tex>i = 3</tex>&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;<tex>+</tex>&nbsp;&nbsp;|-align ="center"|&nbsp;&nbsp;<tex>i =4</tex>&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;|} После того, как посчитана динамика, можно рекурсивно восстановить ответ:* КорменЕсли длина текущего отрезка равна <tex> 1 </tex>, Твыходим из рекурсии*Оборачиваем текущий отрезок <tex> l \ldots r </tex> в скобки*Ставим после элемента последовательности на позиции <tex> d[l][r].index </tex> знак <tex> d[l][r].operation </tex>*Рекурсивно запускаем от отрезков <tex> l \ldots d[l][r].index </tex> и <tex> d[l][r].index + 1 \ldots r </tex>  Таким образом ответ <tex> ((2+1)\times(1+2))</tex> == Решение задачи без возможности использования скобок ==При условии задачи, Лейзерсонв котором запрещено использовать скобки, Чвышеописанный алгоритм будет работать некорректно.Дело в том, Ривестчто если на отрезке <tex>k\ldots j</tex> была использована операция сложения, Рто мы не можем перемножить результаты на отрезке <tex>i\ldots k - 1</tex> и отрезке <tex>k\ldots j</tex>.Для решения этой проблемы будем использовать две матрицы <tex>d</tex> {{---}} такую же как и раньше, Штайна также <tex>p</tex> <tex>(p[i][j]</tex> {{---}} произведение чисел <tex dpi = "130">a_i, a_{i+1}, \ldots, Кa_j)</tex>. Глава 15 Тогда получим новую формулу пересчета динамики:<br />* <tex>d[i][j] = \max\limits_{\mathop{k = i. Динамическое программирование .j-1}}[\max(d[i][k] + d[k + 1][j], p[i][k] \cdot p[k + 1][j])] \ (i < j)</tex> <br / Алгоритмы> == См. также ==*[[Задача о порядке перемножения матриц | Задача о порядке перемножения матриц]]*[[Задача о наибольшей общей подпоследовательности | Задача о наибольшей общей подпоследовательности]] == Источники информации==*[http: построение //fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и анализ = Introduction to Algorithms / Под редрешения {{---}} Классические задачи динамического программирования]* Томас Х. Кормен, Чарльз И. В. КрасиковаЛейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. - 300стр. — М.: Вильямс«Вильямс», 20052007. — 1296 с. 459. — ISBN 5-84598489-0857-4http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm*