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

Решение задачи динамического программирования о сдаче монетами разного номинала

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

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

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

Пример: В некоторой стране имеются монеты достоинством 1, 3, 5 и 10 копеек. Необходимо ответить на вопрос: сколько существует способов вернуть сдачу монетами номиналом n копеек.

* Примечание: 1. порядок монет в сдаче важен, 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 этап: Определение начальных условий

Важно: Одну или две из формул нужно вычислить самостоятельно, без использования рекурсии (в нашем случае это будет F(0) и F(1)), иначе у рекурсии не будет условия для остановки. Этот этап и называется определение начальных условий

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

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

  5. F(3) = 2 способа (F(2) + F(0))
  6. Расшифруем:

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

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

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

     

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

  7. F(4) = F(3) + F(1) = 2 + 1 = 3 способа
  8. Расшифруем:

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

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

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

Задание: самостоятельно просчитайте сколько способов существует для того, чтобы вернуть 6, 7 и 10 копеек сдачи (F(6), F(7), F(10))

задача о сдаче решение

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 <= k <= 3 и для 3 <= 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);

Пример: Запрограммировать решение задачи о количестве способов отдать сдачу номиналом k на языке программирования Pascal. Выполнить задания без использования рекурсии

Показать решение

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)* Ik>=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)* Ik>=i (i ∈ множеству всех монет, т.е. 1, 3, 5, 10)

Важно: Необходимо не забывать, что к формуле нужно добавить условие: F(0)=1, иначе рекурсивная функция будет зацикленной

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

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

Мы сказали, что чтобы вычислить функцию 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)

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

Задание: необходимо решить задачу о сдаче, порядок сдачи монет в которой не важен. Т.е. для сдачи n = 5, способы такие:

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

Решить методом динамического программирования.

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

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить