e-olymp

Динамическое программирование. Базовые понятия.

   Задача 1. Новый Лабиринт Амбера

   Идея решения: Понятно, что в первую ячейку согласно условия мы попасть не можем, поэтому после чтения исходных данных занесем в нее 0, в не зависимости от того, что нам предлагается для неё при считывании исходных данных, а во вторую и третью мы можем попасть единственным образом с начальной  нулевой ячейки. Для всех остальных ячеек у нас есть выбор: попасть в нее либо с ячейки под номером i–2, либо с ячейки под номером  i–3. Выбирать, естественно будем ту, где перед этим уже имеется большая сумма. Схематически это можно изобразить так (на примере с условия задачи):

Номера ячеек

0

1

2

3

4

5

0

1000

2

3

1

3

Содержимое ячеек

    Заменяем содержимое ячейки 1 и начиная с четвертой ячейки, начинаем заниматься решением вопроса, откуда же выгоднее в неё попасть: с ячейки a[i–2] или a[i–3]?

awp_dp01

   Естественно, что выгоднее в ячейку под номером 4 попасть с ячейки под номером 2 (с индексом i–2), так как там уже есть 2 монетки и сумма будет 3, а в ячейке под номером 1 (с индексом i–3) уже накоплено 0 монеток, и сумма будет 1, что является не выгодным. Не заводя дополнительный массив, будем хранить в этой текущей рассматриваемой ячейке найденную сумму, которую формально можно описать так:

awp_dp012

   Тогда при переходе к выбору стратегии перехода в следующей ячейке под номером 5, наш выбор изменится на следующий:

awp_dp02

   Естественно, что и в эту ячейку выгоднее попасть с ячейки с индексом i–2, где хранится монет на единицу больше.  В результате наша таблица будет иметь вид:

              Номера ячеек

0

1

2

3

4

5

0

0

2

3

3

6

Содержимое ячеек

   В результате у нас в конечной (N-той) ячейке всегда будет находится ответ к задаче.

   Описанный выше подход лежит в основе динамического программирования. В основу принципа динамического программирования положено следующую простую стратегию оптимальной политики, указанную Р.Беллманом и названную им принципом оптимальности: „Именно оптимальной политике присуще то свойство, что какими бы не были начальное состояние и первое решение, последующие решения составляют оптимальную политику относительно начального состояния, полученного в результате первого решения.”

   Задача 2. Лесенка

   Идея решения: Решение данной задачи немногим отличается от предыдущей только тем, что на каждую текующую рассматривуемую ступеньку мы можем попасть уже имея выбор не из 2-х возможных, а из K предыдущих ступенек. Этот подход легко реализуется при помощи дополнительного цикла. Чтобы не изменять логику поиска предыдущей программы зададим массив используя ту особенность языка паскаль, что нумеровать массив можно начиная с произвольного индекса. 

   Подсказка: массив чисел, хранящихся на ступеньках, следует объявить как a : array[-1000..1001] of longint;

   Задача 3. Единицы

   Идея решения: Понятно, что для того, чтобы получить число 1 достаточно просто написать одну единицу, а число 2 получается путем сложения двух еиниц. Дальнейшая логика такова: мы можем любое следующее число найти, прибавив к предыдущему одну единицу (a[k] = a[k-1] + 1) - это и есть первое приближение оптимального решения. После этого пробуем число k разложить на два множителя, и если это удалось, то сума единиц, входящих в каждый из сомножителей проверятся с текущим оптимальным значением a[k], если найденное число оказывется меньшим, естественно принимаем его за оптимальное. Искать разложение достаточно до sqrt(k).

   Задача 4. Paint2D

   Идея решения: Идею решения данной задачи разберем более детально.

(Продолжение следует)