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

Задача:

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

Решение

Данная задача решается с использованием принцип оптимальности на подотрезках. Введём матрицу [math]d[/math] размером [math]n \times n[/math], где [math]d[i][j][/math] будет равен максимальному значению, достигаемому на подотрезке [math]a_i, a_{i+1}, \dots, 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] \times 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] \times d[k+1][j]))[/math];

Реализация

 // d - матрица как в описании; a - последовательность из n элементов; i, j, k - счётчики
 
 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(d[1][n]); // вывод ответа

Пример

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

	j = 1	j = 2	j = 3	j = 4
i = 1	2	3	4	9
i = 2	0	1	2	4
i = 3	0	0	1	3
i = 4	0	0	0	2

Источники

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. - 300стр. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm