Поиск максимальной суммы

Введение

Динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Отметим, что алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи — на более мелкие подзадачи и так далее, а затем собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подподзадачи по нескольку раз. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.

В типичном случае динамическое программирование применяется к задачам оптимизации. У такой задачи может быть много возможных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи) Вообще говоря, оптимум может достигаться для нескольких разных решении.

Для построения алгоритма, основанного на динамическом программировании, надо:

1) описать строение оптимальных решений;

2) выписать рекуррентное соотношение, связывающее оптимальные значения параметра для подзадач;

3) двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач;

4) пользуясь полученной информацией, построить оптимальное решение.

Основную часть работы составляют шаги 1-3. Если нас интересует толь оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим для построения оптимального решения, иногда приходится получать и дополнительную информацию в процессе выполнения шага 3.

Одна из простейших задач, иллюстрирующих применение динамическое программирование, следующая.

На прямоугольной доске расставлены целые неотрицательные числа . Нужно проложить маршрут из левого верхнего угла (1,1) в правый нижний . При этом можно передвигаться только в соседнюю клетку справа или снизу. Требуется, чтобы сумма всех чисел, оказавшихся на пути, была бы максимальной.

Для решения задачи введем вспомогательную величину - это максимальная сумма, которую можно набрать, если маршрут заканчивается в клетке . Тогда максимальная сумма всех чисел, оказавшихся на пути до правого нижнего угла, будет . Найдем способы подсчета величин .

Очевидно, что .

В клетку первой строки (для которой ) можно попасть только из клетки слева (это клетка ), следовательно, .

В клетку первого столбца (для которой ) можно попасть только из клетки сверху (это клетка ), следовательно, .

Во все остальные клетки (для которых ) можно попасть как из клетки слева, так и из клетки сверху, поэтому .

Теперь несложно рассчитать значения для всех . Таблица заполняется построчно сверху вниз. Каждая строка заполняется справа налево с применением соответствующей формулы в зависимости от значений .

Как видно, оптимальный путь в клетку включает в себя оптимальный путь в клетку с меньшими индексами, т.е. оптимальное решение задачи содержит оптимальные решения её подзадач. Это один из признаков, характерных для задач, решаемых методом динамического программирования.