Презентация на тему: Динамическое программирование

Реклама. Продолжение ниже
Динамическое программирование
Что такое ДП?
Представление ДП
Задача 1
Реализация
Задача 2?
Задача 2
Задача о рюкзаке
Задача о рюкзаке
Задача о рюкзаке. Шаг 1
Задача о рюкзаке. Шаг 2
Задача о рюкзаке. Шаг 3
Задача о рюкзаке. Шаг 4
Задача о рюкзаке. Шаг 8
Задача о рюкзаке. Шаг 9
Задача о рюкзаке. Шаг 10
Задача о рюкзаке. Шаг 11
Задача о рюкзаке. Шаг 12
Задача о рюкзаке. Шаг 13
Задача о рюкзаке. Шаг 14
Задача о рюкзаке. Шаг 15
Задача о рюкзаке. Шаг 16
Задача о рюкзаке. Шаг 17
Задача о рюкзаке. Шаг 18
Задача о рюкзаке. Шаг 19
Задача о рюкзаке. Шаг 20
Задача о рюкзаке. Шаг 21
Задача о рюкзаке. Шаг 22
Задача о рюкзаке. Итоговая матрица
Задача о рюкзаке. Оптимизация
Оптимизированный рюкзак с повторениями
Оптимизированный рюкзак без повторений
1/32
Средняя оценка: 4.9/5 (всего оценок: 58)
Код скопирован в буфер обмена
Скачать (286 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Динамическое программирование

Школа::Кода Олимпиадное программирование 2020-2021 Таганрог

Изображение слайда
Изображение для работы со слайдом
1/2
2

Слайд 2: Что такое ДП?

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

Изображение слайда
1/1
3

Слайд 3: Представление ДП

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

Изображение слайда
1/1
4

Слайд 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.

Изображение слайда
Изображение для работы со слайдом
1/2
5

Слайд 5: Реализация

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

Изображение слайда
Изображение для работы со слайдом
Изображение для работы со слайдом
Изображение для работы со слайдом
1/4
6

Слайд 6: Задача 2?

Есть лестница длиной N ступенек. За 1 шаг вы можете подняться на 1 или 2 ступеньки вверх. Изначально вы стоите перед первой ступенькой. Сколько существует различных способов подняться по лестнице? Номер ступеньки – параметр состояния. Количество способов подняться на ступеньку – значение состояния. Начальное значение dp [0] = 1. На ступеньку k можно перейти со ступенек k – 1 и k – 2.

Изображение слайда
1/1
7

Слайд 7: Задача 2

Есть лестница длиной N ступенек, на каждой ступеньке написано положительное число A k. За 1 шаг вы можете подняться на 1 или 2 ступеньки вверх, когда вы становитесь на ступеньку, к результату прибавляется число, написанное на ней. Изначально вы стоите перед первой ступенькой. Какой максимальный результат вы можете получить при подъёме по лестнице? Номер ступеньки – параметр состояния. Максимальный результат, который можно набрать, поднявшись до определённой ступеньки – значение состояния. Начальное значение dp = {0, … 0}. На ступеньку k можно перейти со ступенек k – 1 и k – 2, следовательно dp [k] = max( dp [k – 1], dp [k – 2]) + A k.

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Задача о рюкзаке

Есть рюкзак объёмом V и N предметов, каждый из которых имеет объём A i. Какой максимальный объём рюкзака можно заполнить? dp [‘ количество рассмотренных предметов ’] [‘ набранный объём ’] = = 0, если состояние недостижимо, иначе 1 Начальное значение: dp [ 0 ][0] = 1 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Идея: сначала определим, какой объём рюкзака можно заполнить используя только первый предмет. Затем определим, какой объём можно заполнить добавив второй предмет, и т.д. Ответ: максимальное j, такое что dp [N][j] = 1

Изображение слайда
1/1
9

Слайд 9: Задача о рюкзаке

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 2 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Создадим матрицу dp [N + 1][V + 1]. Пусть изначально её элементы равны 0, за исключением dp [0][0] = 1. Будем проходить по всем элементам матрицы, начиная со строки 1 и пересчитывать значения, согласно переходам.

Изображение слайда
1/1
10

Слайд 10: Задача о рюкзаке. Шаг 1

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 2 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 1

Изображение слайда
1/1
11

Слайд 11: Задача о рюкзаке. Шаг 2

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0 3 2 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 2

Изображение слайда
1/1
12

Слайд 12: Задача о рюкзаке. Шаг 3

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 0 0 0 0 0 3 2 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 3

Изображение слайда
1/1
13

Слайд 13: Задача о рюкзаке. Шаг 4

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 4

Изображение слайда
1/1
14

Слайд 14: Задача о рюкзаке. Шаг 8

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 8

Изображение слайда
1/1
Реклама. Продолжение ниже
15

Слайд 15: Задача о рюкзаке. Шаг 9

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 9

Изображение слайда
1/1
16

Слайд 16: Задача о рюкзаке. Шаг 10

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 10

Изображение слайда
1/1
17

Слайд 17: Задача о рюкзаке. Шаг 11

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 0 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 11

Изображение слайда
1/1
18

Слайд 18: Задача о рюкзаке. Шаг 12

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 12

Изображение слайда
1/1
19

Слайд 19: Задача о рюкзаке. Шаг 13

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 0 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 13

Изображение слайда
1/1
20

Слайд 20: Задача о рюкзаке. Шаг 14

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 14

Изображение слайда
1/1
21

Слайд 21: Задача о рюкзаке. Шаг 15

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 0 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 15

Изображение слайда
1/1
22

Слайд 22: Задача о рюкзаке. Шаг 16

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 0 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 16

Изображение слайда
1/1
23

Слайд 23: Задача о рюкзаке. Шаг 17

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 0 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 17

Изображение слайда
1/1
24

Слайд 24: Задача о рюкзаке. Шаг 18

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 1 0 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 18

Изображение слайда
1/1
25

Слайд 25: Задача о рюкзаке. Шаг 19

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 1 1 0 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 19

Изображение слайда
1/1
26

Слайд 26: Задача о рюкзаке. Шаг 20

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 1 1 1 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 20

Изображение слайда
1/1
27

Слайд 27: Задача о рюкзаке. Шаг 21

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 1 1 1 0 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 21

Изображение слайда
1/1
28

Слайд 28: Задача о рюкзаке. Шаг 22

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 1 1 1 1 0 Переход: dp [ i ][j] = max( dp [ i – 1][j], dp [ i – 1][j – A i ]) Задача о рюкзаке. Шаг 22

Изображение слайда
1/1
29

Слайд 29: Задача о рюкзаке. Итоговая матрица

j 0 1 2 3 4 5 6 i А 0 1 0 0 0 0 0 0 2 1 1 0 1 0 0 0 0 3 2 1 0 1 1 0 1 0 1 3 1 1 1 1 1 1 1 Ответ: 6 Задача о рюкзаке. Итоговая матрица

Изображение слайда
1/1
30

Слайд 30: Задача о рюкзаке. Оптимизация

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

Изображение слайда
1/1
31

Слайд 31: Оптимизированный рюкзак с повторениями

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

Изображение слайда
1/1
32

Последний слайд презентации: Динамическое программирование: Оптимизированный рюкзак без повторений

Если же каждый предмет дан в единственном экземпляре, то для предотвращения повторений достаточно изменить порядок обхода массива и перебирать j от V до 0. j 0 1 2 dp 1 0 0 j 0 1 2 dp 1 0 0 j 0 1 2 dp 1 1 0 A 0 = 1

Изображение слайда
1/1
Реклама. Продолжение ниже