Занятие 2. Решение задач ДП

Задача о сдаче

В предыдущем примере решение задачи при помощи ДП было излишним и искусственным. Но для простоты мы взяли эту задачу.

Решим еще одну задачу чуть более сложную.

Разбор задачи:
Предположим нужно вернуть сдачу 4 копейки. Выделим всевозможные способы:

1. 1 1 1 1
2. 1 3
3. 3 1

Заметим, что 2 и 3 способ — это разные способы, т.к. порядок в нашей задаче важен.

Ответим на вопрос, сколько способов для того, чтобы вернуть:

• 1 копейку? — 1 способ
• 0 копеек? — 1 способ (каждого номинала монет необходимо вернуть по 0 способу)

В этой задаче ДП — не самый эффективный способ, но решим при помощи него.

Решение:

Так как важен порядок монет, то решим так:

1 этап: Обозначение целевой функции

Обозначим через F(i) кол-во способов вернуть сдачу размера i (F(n) — целевая функция — ответ на нашу задачу, т.е. кол-во способов вернуть сдачу размера n)

2 этап: Определение порядка решения

Порядок решения: Выполнять задачу будем линейно, т.е. начиная с самой простой и постепенно усложняя ее (с F(1) до F(n)). Хотя можно решать задачи ДП и не линейно, а, например, при помощи дерева.

Начнем с самой простой подзадачи. Предположим, что существует только монета номиналом 1 копейка. F(1) = 1.

Результат функции F(1) мы знаем, он равен 1; используя знания о F(1), вычислим F(2), используя знания о F(2), найдем F(3) …. и т.д.

F(1) <- F(2) <- F(3) ... F(n-1) <- F(n)

*можно в самом начале добавить F(0), F(0)=1.

3 этап: Определение начальных условий

Итак получаем:

1. F(0) = 1 способ вернуть 0 копеек
2. F(1) = 1 способ вернуть 1 копейку
3. F(2) = F(1) - 1 способ вернуть 2 копейки

Здесь расшифруем: 2 копейки получим так: 1 копейка возвращается + 1 копейку осталось вернуть сдачей (F(1)), т.е. один способ

4. F(3) = 2 способа (F(2) + F(0))

Расшифруем:

• 1 копейка возвращается + 2 копейки (т.е. 2 копейки - функция F(2))

ИЛИ

• 3 копейки возвращаются + 0 копеек (т.е. 0 копеек - ф-ция F(0))

Получаем:
F(3) = F(2) + F(0) = 1 + 1 = 2 способа - > стоит сложение потому что логическое ИЛИ


Пояснение к рисунку: в прямоугольниках обозначены функции, в окружностях - монеты.

5. F(4) = F(3) + F(1) = 2 + 1 = 3 способа

Расшифруем:

• сначала отдаем 1 копейку + остается вернуть 3 (= F(3))
• сначала отдаем 3 копейки + остается вернуть 1 (= F(1))

т.е. как мы и рассчитывали в начале занятия:

1. 1 1 1 1
2. 1 3
3. 3 1
6. F(5) = F(4) + F(2) + F(0) = 3 + 1 + 1 = 5 способов

4 этап: Вычисление и нахождение общей формулы

Напишем формулу в общем виде для F(k), где k >= 10

Рассмотрим способы:

• даем сдачу 1 копейка + остается дать сдачу k-1 копейка

∨ (ИЛИ)

• даем сдачу 3 копейки + остается дать сдачу k-3 копейки

∨

• даем сдачу 5 копеек + остается дать сдачу k-5 копеек

∨

• даем сдачу 10 копеек + остается дать сдачу k-10 копеек

Получаем формулу в общем виде:
F(k) = F(k-1) + F(k-3) + F(k-5) + F(k-10)

Эта формула действительна для k >= 10

Аналогично посчитаем формулу для 5 <= k <= 10:

F(k) = F(k-1) + F(k-3) + F(k-5)

Таким образом, выделим этапы решения задачи:

1. определение целевой функции: F(i)
2. определение порядка решения:
   F(0) <- F(1) <- F(2) <- F(3) ... F(n-1) <- F(n)
3. определение начальных условий: F(0) = 1, F(1) = 1, F(2) = 1, F(4) = F(3) + F(1), F(5) = F(4) + F(2) + F(0)
4. вычисление и нахождение общей формулы:
   для k>=10:
   F(k) = F(k-1) + F(k-3) + F(k-5) + F(k-10)
   для 3 <= k < 5: f(k) = f(k-1) + f(k-3);
   для 5 <= k < 10: f(k) = f(k-1) + f(k-3) + f(k-5);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var f: array[0..100]of integer;
  i,k:integer;
  procedure kol_sposobov(k: integer);
  begin
// определение начальных условий:
  f[0]:=1;
  f[1]:=1;
  f[2]:=1;
 
//порядок решения от простого к сложному, от f(3) до f(k)
       for i:=3 to k do begin 
       // использование общей формулы для различных k
       if (i>=3) and (i<5) then
           f[i]:=f[i-1]+f[i-3];
       if (i>=5) and (i<10)then
           f[i]:=f[i-1]+f[i-3]+f[i-5];
       if (i>=10) then
           f[i]:=f[i-1]+f[i-3]+f[i-5]+f[i-10];
       writeln (' для i=', i, ' способов=',f[i]);
       end;
  end;
  begin
  writeln ('введите размер сдачи k ');
  readln(k);
  kol_sposobov(k);
  end.

Перевод в формулу индикатор

Функцию F(n) легко перевести в функцию-индикатор:
функция равняется событию, если оно произошло, и функция не равняется событию, если оно не произошло:

Переведем и получаем:
F(k) = F_(k-10) * I_(k>=10) + F_(k-5) * I_(k>=5) + F_(k-3)* I_(k>=3) + F_(k-1) * I_(k>=1) =
∑ F(k-i)* I_k>=i (i ∈ множество всех монет)

В случае, когда k>=10 получим:
Первое слагаемое: F_(k-10) * на индикатор того, что k>=10, т.е. если в задаче действительно k>=10, то индикатор вернет единицу (истина), и первое слагаемое будет присутствовать в формуле;

Второе слагаемое: F_(k-5) (оно должно присутствовать в формуле лишь тогда, когда k>=5) * на индикатор того, что k>=5, т.е. если в задаче действительно k>=5, то индикатор вернет единицу (истина), и второе слагаемое будет присутствовать в формуле;
… и .т.д.

Таким образом, используя функцию индикатор можно несколько формул (в нашем случае 4) заменить на одну формулу:

• формула для n>=10,
• формула для 5<=n<=10,
• формула для 3<=n<=5,
• формула для 1<=n<=3

заменили на формулу:
F(k) = F_(k-10) * I_(k>=10) + F_(k-5) * I_(k>=5) + F_(k-3)* I_(k>=3) + F_(k-1) * I_(k>=1)
или, если сжать формулу:
∑ F(k-i)* I_k>=i (i ∈ множеству всех монет, т.е. 1, 3, 5, 10)

Сложность и эффективность решения

Попытаемся проанализировать эффективность нашего решения, т.е. его временные условия.

Мы сказали, что чтобы вычислить функцию F(n), нужно вычислить F(0), F(1), F(2) и т.д. Т.е. в нашей цепочке мы сделаем n переходов (F(0) <- F(1) <- F(2) <- F(3) … F(n-1) <- F(n))

А сколько «стоит» каждый переход? На каждом шаге мы считаем сумму, в которой максимум будет 4 слагаемых (т.е. 4 операции):

F(k) = F_(k-10) * I_(k>=10) + F_(k-5) * I_(k>=5) + F_(k-3)* I_(k>=3) + F_(k-1) * I_(k>=1)

Как правило, сложность работы алгоритма формулируется, как функция от длины входных данных алгоритма.

Что у нас является входными данными? — это набор монет (1, 2, 5, 10) и размер сдачи, который мы должны вернуть (например, 10 копеек).

Допустим, размер сдачи = n, тогда мы записываем log от n
Т.е. сложность нашего алгоритма: 𝜭(lg n)

Время работы данного алгоритма не линейно, а экспоненциально (достаточно «жадный» алгоритм). Т.е. выполненное решение с точки зрения занимаемого времени не эффективно.

Но существует и эффективное решение данной задачи, это уже задачи комбинаторики.