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

Материал из Викиконспекты
Перейти к: навигация, поиск

Задача о расстановке знаков в выражении — задача о нахождении максимального значения выражения, полученного расстановкой знаков [math]+, \times[/math] и скобок в последовательности [math]a_1, a_2, \dots, a_n \ (a_i \ge 0)[/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_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k]*d[k+1][j])] \ (i \lt j)[/math]

Вычислим элементы таблицы [math]d[/math], тогда ответом на задачу будет значение [math]d[1][n][/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