Задача о расстановке знаков в выражении

Задача:

Пусть задана последовательность неотрицательных чисел [math]a_1, a_2, \ldots, a_n \ (a_i \geqslant 0)[/math]. Требуется расставить знаки [math]+, \times[/math] и скобки в последовательности, чтобы значение полученного арифметического выражения было максимальным.

Решение

Данная задача решается с использованием принципа оптимальности на подотрезках. Введём матрицу [math]d[/math] размером [math]n \times n[/math], где [math]d[i][j][/math] будет равен максимальному значению, достигаемому на подотрезке [math]a_i, a_{i+1}, \ldots, a_j[/math]. Получаем следующие соотношения:

• [math]d[i][i] = a_i [/math]
  
• [math]d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k] \cdot d[k+1][j])] \ (i \lt j)[/math]
  

Вычислим элементы таблицы [math]d[/math], тогда ответом на задачу будет значение [math]d[1][n][/math].

Доказательство

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

Реализация

 // a - заданная последовательность из n элементов
 
 int maxValueOfExpression(a, n):
   for i = 1 to n:
     d[i][i] = a[i]
 
   for i = n - 1 downto 1:
     for j = i + 1 to n:
       for k = i to j - 1:
         d[i][j] = max(d[i][j], max(d[i][k] + d[k + 1][j], d[i][k] * d[k + 1][j]))
   return d[1][n]

Пример

Пусть дана последовательность [math]2, 1, 1, 2[/math]. Таблица [math]d[/math] для неё будет выглядеть так:

	[math]j = 1[/math]	[math]j = 2[/math]	[math]j = 3[/math]	[math]j = 4[/math]
[math]i = 1[/math]	[math]2[/math]	[math]3[/math]	[math]4[/math]	[math]9[/math]
[math]i = 2[/math]	[math]0[/math]	[math]1[/math]	[math]2[/math]	[math]4[/math]
[math]i = 3[/math]	[math]0[/math]	[math]0[/math]	[math]1[/math]	[math]3[/math]
[math]i = 4[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]2[/math]

Восстановление ответа

С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице [math]d[/math] хранить каким способом был получен оптимальный ответ. То есть будем хранить [math]index[/math] — границу раздела на 2 подотрезка [math](i \ldots index[/math] и [math]index + 1 \ldots j)[/math] и [math]operation[/math] — операцию совершенную над двумя отрезками ([math]+, \times[/math]). В итоге для каждого отрезка мы будем знать какой знак и куда поставить. Для простоты будем заключать каждый полученный подотрезок в скобки. Таким образом мы получим выражение, в котором полностью расставлены скобки.

Для вышеприведенного примера таблица будет выглядеть так:

[math]index[/math]	[math]j = 1[/math]	[math]j = 2[/math]	[math]j = 3[/math]	[math]j = 4[/math]
[math]i = 1[/math]	[math]-[/math]	[math]1[/math]	[math]1[/math]	[math]2[/math]
[math]i = 2[/math]	[math]-[/math]	[math]-[/math]	[math]2[/math]	[math]3[/math]
[math]i = 3[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]	[math]3[/math]
[math]i = 4[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]

[math]operation[/math]	[math]j = 1[/math]	[math]j = 2[/math]	[math]j = 3[/math]	[math]j = 4[/math]
[math]i = 1[/math]		[math]+[/math]	[math]\times[/math]	[math]\times[/math]
[math]i = 2[/math]			[math]+[/math]	[math]\times[/math]
[math]i = 3[/math]				[math]+[/math]
[math]i = 4[/math]

После того, как посчитана динамика, можно рекурсивно восстановить ответ:

• Если длина текущего отрезка равна [math] 1 [/math], выходим из рекурсии
• Оборачиваем текущий отрезок [math] l \ldots r [/math] в скобки
• Ставим после элемента последовательности на позиции [math] d[l][r].index [/math] знак [math] d[l][r].operation [/math]
• Рекурсивно запускаем от отрезков [math] l \ldots d[l][r].index [/math] и [math] d[l][r].index + 1 \ldots r [/math]

Таким образом ответ [math] ((2+1)\times(1+2))[/math]

Решение задачи без возможности использования скобок

При условии задачи, в котором запрещено использовать скобки, вышеописанный алгоритм будет работать некорректно. Дело в том, что если на отрезке [math]k\ldots j[/math] была использована операция сложения, то мы не можем перемножить результаты на отрезке [math]i\ldots k - 1[/math] и отрезке [math]k\ldots j[/math]. Для решения этой проблемы будем использовать две матрицы [math]d[/math] — такую же как и раньше, а также [math]p[/math] [math](p[i][j][/math] — произведение чисел [math]a_i, a_{i+1}, \ldots, a_j)[/math]. Тогда получим новую формулу пересчета динамики:

• [math]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 \lt j)[/math]
  

См. также

• Задача о порядке перемножения матриц
• Задача о наибольшей общей подпоследовательности

Источники информации

• Олимпиадные задачи и решения — Классические задачи динамического программирования
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4