Викиконспекты - Вклад участника [ru]

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

2017-06-04T22:03:10Z

Ruslan02: /* Реализация */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \ldots, a_n \ (a_i \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}, \ldots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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] \cdot d[k+1][j]))</tex>;

== Реализация ==
// 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]

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

== Восстановление ответа ==
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <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"
|  <tex>index</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>-</tex>  
|  <tex>1</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|}

:{| border = 1; class="wikitable"
|-align = "center"
|  <tex>operation</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|    
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|    
|    
|    
|  <tex>+</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|    
|    
|    
|    
|}

После того, как посчитана динамика, можно рекурсивно восстановить ответ:
*Если длина текущего отрезка равна <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>. Тогда получим новую формулу пересчета динамики:
 
* <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> 

== См. также ==
*[[Задача о порядке перемножения матриц | Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности | Задача о наибольшей общей подпоследовательности]]

== Источники информации==
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T21:54:48Z

Ruslan02:

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \ldots, a_n \ (a_i \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}, \ldots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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] \cdot d[k+1][j]))</tex>;

== Реализация ==
// 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]

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

== Восстановление ответа ==
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <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"
|  <tex>index</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>-</tex>  
|  <tex>1</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|}

:{| border = 1; class="wikitable"
|-align = "center"
|  <tex>operation</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|    
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|    
|    
|    
|  <tex>+</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|    
|    
|    
|    
|}

После того, как посчитана динамика, можно рекурсивно восстановить ответ:
*Если длина текущего отрезка равна <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>. Тогда получим новую формулу пересчета динамики:
 
* <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> 

== См. также ==
*[[Задача о порядке перемножения матриц | Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности | Задача о наибольшей общей подпоследовательности]]

== Источники информации==
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T21:50:09Z

Ruslan02: /* Восстановление ответа */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \ldots, a_n \ (a_i \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}, \ldots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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] \cdot d[k+1][j]))</tex>;

== Реализация ==
// 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]

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

== Восстановление ответа ==
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <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"
|  <tex>index</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>-</tex>  
|  <tex>1</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|}

:{| border = 1; class="wikitable"
|-align = "center"
|  <tex>operation</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|    
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|    
|    
|    
|  <tex>+</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|    
|    
|    
|    
|}

После того, как посчитана динамика, можно рекурсивно восстановить ответ:
*Если длина текущего отрезка равна <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>. Тогда получим новую формулу пересчета динамики:
 
* <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> 

== Источники информации==
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T21:41:34Z

Ruslan02:

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \ldots, a_n \ (a_i \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}, \ldots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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] \cdot d[k+1][j]))</tex>;

== Реализация ==
// 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]

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

== Восстановление ответа ==
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <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"
|  <tex>index</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>-</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>2</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|  <tex>-</tex>  
|}

:{| border = 1; class="wikitable"
|-align = "center"
|  <tex>operation</tex>  
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|    
|    
|  <tex>+</tex>  
|  <tex>\times</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|    
|    
|    
|  <tex>+</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|    
|    
|    
|    
|}

После того, как посчитана динамика, можно рекурсивно восстановить ответ:
*Если длина текущего отрезка равна <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>. Тогда получим новую формулу пересчета динамики:
 
* <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> 

== Источники информации==
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T19:39:43Z

Ruslan02:

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 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}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

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

'''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]));

'''print'''(d[1][n]); // вывод ответа

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

== Восстановление ответа ==
С помощью описанного выше алгоритма можно восстановить оптимальное арифметическое выражение. Для этого нужно в таблице <tex>d</tex> хранить каким способом был получен оптимальный ответ. То есть будем хранить <tex>index</tex> {{---}} границу раздела на 2 подотрезка и <tex>operation</tex> {{---}} операцию совершенную над двумя отрезками (<tex>+, \times</tex>). В итоге для каждого отрезка мы будем знать какой знак и куда поставить. Для простоты будем заключать каждый полученный подотрезок в скобки. Таким образом мы получим выражение, в котором полностью расставлены скобки.

Для вышеприведенного примера ответ будет выглядеть так <tex> (2+1)\times(1+2)</tex>

== Решение задачи без возможности использования скобок ==
При условии задачи, в котором запрещено использовать скобки, вышеописанный алгоритм будет работать некорректно. Дело в том, что если на отрезке <tex>k\dots j</tex> была использована операция сложения, то мы не можем перемножить результаты на отрезке <tex>i\dots k - 1</tex> и отрезке <tex>k\dots j</tex>. Для решения этой проблемы будем использовать две матрицы <tex>d</tex> {{---}} такую же как и раньше, а также <tex>p</tex> <tex>(p[i][j]</tex> {{---}} произведение чисел <tex dpi = "130">a_i, a_{i+1}, \dots, a_j)</tex>. Тогда получим новую формулу пересчета динамики:
 
* <tex>d[i][j] = \max\limits_{\mathop{k = i..j-1}}[\max(d[i][k] + d[k + 1][j], p[i][k] \times p[k + 1][j])] \ (i < j)</tex> 

== Источники ==
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T18:00:23Z

Ruslan02: /* Источники */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 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}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

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

'''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]));

'''print'''(d[1][n]); // вывод ответа

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

== Источники ==
*[http://fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rules22.htm Олимпиадные задачи и решения {{---}} Классические задачи динамического программирования]

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T17:51:32Z

Ruslan02: /* Реализация */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 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}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

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

'''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]));

'''print'''(d[1][n]); // вывод ответа

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T17:51:03Z

Ruslan02: /* Реализация */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 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}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

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

'''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]));

'''write'''(d[1][n]); // вывод ответа

== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T17:43:53Z

Ruslan02: /* Пример */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 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}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

== Реализация ==
// 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]); // вывод ответа
== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>2</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T17:42:52Z

Ruslan02: /* Пример */

{{ Задача
|definition =
Пусть задана последовательность неотрицательных чисел <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 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}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.

== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

== Реализация ==
// 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]); // вывод ответа
== Пример ==
Пусть дана последовательность <tex>2, 1, 1, 2</tex>. Таблица <tex>d</tex> для неё будет выглядеть так:

:{| border = 1; class="wikitable"
|-align = "center"
|    
|  <tex>j = 1</tex>  
|  <tex>j = 2</tex>  
|  <tex>j = 3</tex>  
|  <tex>j = 4</tex>  
|-align = "center"
|  <tex>i = 1</tex>  
|  <tex>3</tex>  
|  <tex>3</tex>  
|  <tex>4</tex>  
|  <tex>9</tex>  
|-align = "center"
|  <tex>i = 2</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>2</tex>  
|  <tex>4</tex>  
|-align = "center"
|  <tex>i = 3</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>1</tex>  
|  <tex>3</tex>  
|-align = "center"
|  <tex>i = 4</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>0</tex>  
|  <tex>2</tex>  
|}

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T17:33:20Z

Ruslan02: /* Решение */

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

2017-06-04T17:33:01Z

Ruslan02: /* Решение */

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

2017-06-04T17:28:55Z

Ruslan02: /* Доказательство */

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

== Решение ==
Данная задача решается с использованием принципа оптимальности на подотрезке[http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D0.BE.D0.B4.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.B0.D1.85]. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dots, a_j</tex>.
Получаем следующие соотношения: 
* <tex>d[i][i] = a_i </tex> 
* <tex>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 < j)</tex> 
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.
== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции <tex>+</tex> и <tex>\times</tex>, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с <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 d[k+1][j]))</tex>;

== Реализация ==
// 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. Таблица <tex>d</tex> для неё будет выглядеть так:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || 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
*

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2017-06-04T17:21:06Z

Ruslan02: