Динамическое программирование

Август 12, 2022

Главная
Информатика
Динамическое программирование

Содержание

2. Что такое ДП? Динамическое программирование – это когда у нас есть задача, которую непонятно как решать,
3. Представление ДП ДП представляют в виде набора состояний. Каждое состояние имеет параметры. Каждому набору параметров соответствует
4. Задача 1 Дано число N требуется вычислить N-е число Фибоначчи. По определению f(N) = f(N –
5. Реализация Ленивая динамика Прямой пересчёт Обратный пересчёт
6. Задача 2? Есть лестница длиной N ступенек. За 1 шаг вы можете подняться на 1 или
7. Задача 2 Есть лестница длиной N ступенек, на каждой ступеньке написано положительное число Ak. За 1
8. Задача о рюкзаке Есть рюкзак объёмом V и N предметов, каждый из которых имеет объём Ai.
9. Задача о рюкзаке Создадим матрицу dp[N + 1][V + 1]. Пусть изначально её элементы равны 0,
10. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 1
11. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 2
12. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 3
13. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 4
14. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 8
15. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 9
16. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 10
17. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 11
18. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 12
19. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 13
20. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 14
21. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 15
22. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 16
23. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 17
24. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 18
25. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 19
26. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 20
27. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 21
28. Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai]) Задача о рюкзаке. Шаг 22
29. Ответ: 6 Задача о рюкзаке. Итоговая матрица
30. Задача о рюкзаке. Оптимизация Базовый алгоритм имеет асимптотику O(N*V) и требует N*V памяти. Однако, можно заметить,
31. Оптимизированный рюкзак с повторениями Заметим, что если мы будем перебирать j от 0 до V, то
33. Скачать презентацию

Слайд 2

Что такое ДП?
Динамическое программирование – это когда у нас есть задача,

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

Слайд 3

Представление ДП
ДП представляют в виде набора состояний.
Каждое состояние имеет параметры. Каждому

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

Слайд 4

Задача 1
Дано число N требуется вычислить N-е число Фибоначчи.
По определению f(N)

= f(N – 1) + f(N – 2), f(0) = 1, f(1) = 1.

С точки зрения ДП:
n – это параметр состояния, f(n) – значение состояния;
В состояние k существуют переходы из состояний k – 1 и k – 2, такие что dp[k] = dp[k – 1] + dp[k – 2];
Начальные значения – dp[0] = 1, dp[1] = 1.

Слайд 5

Реализация
Ленивая динамика
Прямой пересчёт
Обратный пересчёт

Слайд 6

Задача 2?
Есть лестница длиной N ступенек.
За 1 шаг вы можете подняться

на 1 или 2 ступеньки вверх.
Изначально вы стоите перед первой ступенькой.
Сколько существует различных способов подняться по лестнице?

Номер ступеньки – параметр состояния.
Количество способов подняться на ступеньку – значение состояния.
Начальное значение dp[0] = 1.
На ступеньку k можно перейти со ступенек k – 1 и k – 2.

Слайд 7

Задача 2
Есть лестница длиной N ступенек, на каждой ступеньке написано положительное

число Ak.
За 1 шаг вы можете подняться на 1 или 2 ступеньки вверх, когда вы становитесь на ступеньку, к результату прибавляется число, написанное на ней.
Изначально вы стоите перед первой ступенькой.
Какой максимальный результат вы можете получить при подъёме по лестнице?

Номер ступеньки – параметр состояния.
Максимальный результат, который можно набрать, поднявшись до определённой ступеньки – значение состояния.
Начальное значение dp = {0, … 0}.
На ступеньку k можно перейти со ступенек k – 1 и k – 2, следовательно dp[k] = max(dp[k – 1], dp[k – 2]) + Ak.

Слайд 8

Задача о рюкзаке
Есть рюкзак объёмом V и N предметов, каждый из

которых имеет объём Ai. Какой максимальный объём рюкзака можно заполнить?

dp[‘количество рассмотренных предметов’] [‘набранный объём’] = = 0, если состояние недостижимо, иначе 1

Начальное значение: dp[0][0] = 1

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])

Идея: сначала определим, какой объём рюкзака можно заполнить используя только первый предмет. Затем определим, какой объём можно заполнить добавив второй предмет, и т.д.

Ответ: максимальное j, такое что dp[N][j] = 1

Слайд 9

Задача о рюкзаке
Создадим матрицу dp[N + 1][V + 1]. Пусть изначально её

элементы равны 0, за исключением dp[0][0] = 1. Будем проходить по всем элементам матрицы, начиная со строки 1 и пересчитывать значения, согласно переходам.

Слайд 10

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 1

Слайд 11

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 2

Слайд 12

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 3

Слайд 13

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 4

Слайд 14

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 8

Слайд 15

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 9

Слайд 16

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 10

Слайд 17

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 11

Слайд 18

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 12

Слайд 19

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 13

Слайд 20

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 14

Слайд 21

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 15

Слайд 22

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 16

Слайд 23

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 17

Слайд 24

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 18

Слайд 25

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 19

Слайд 26

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 20

Слайд 27

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 21

Слайд 28

Переход: dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – Ai])
Задача

о рюкзаке. Шаг 22

Слайд 29

Ответ: 6
Задача о рюкзаке. Итоговая матрица

Слайд 30

Задача о рюкзаке. Оптимизация
Базовый алгоритм имеет асимптотику O(NV) и требует NV

памяти. Однако, можно заметить, что при переходе мы не можем ухудшить уже имеющийся результат, что позволяет провести вычисления на одномерном массиве.
Перейдём от матрицы dp[N + 1][V + 1] к массиву dp[V + 1].
Теперь для пересчёта будем пользоваться формулой dp[j] = max(dp[j], dp[j - Ai]).

Слайд 31

Оптимизированный рюкзак с повторениями
Заметим, что если мы будем перебирать j от

0 до V, то может произойти ситуация, когда значение dp[j - Ai] стало равно 1 при использовании предмета с номером i. В таком случае значение dp[j] так же станет равно 1, а это будет означать что мы использовали предмет с номером i уже несколько раз. Такой порядок обхода применяется, когда в условии сказано, что у вас есть неограниченное количество каждого предмета.

A0 = 1