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

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

Рейтинг за домашнюю работу

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

Задача про черепашку Есть клетчатое поле NхM. В левом верхнем углу сидит черепашка. Она умеет ходить только вправо или вниз. А) Сколько у неё разных путей до правого нижнего угла?

Первая основная идея ДП Будем искать ответ не только на нашу общую задачу, но и на более мелкие аналогичные задачи («подзадача»). В нашем случае решим для каждой клетки поля сколькими способами до неё можно добраться.

А что дальше? Ответ для верхнего левого угла очевиден. У нас только один способ до него добраться. Для клеток левого столбца и верхней строки тоже всё очевидно.

Вторая основная идея ДП Решая задачу для очередной клетки, будем считать, что мы уже знаем ответ для предыдущих клеток и попробуем, используя это знание, найти ответ для текущей.

А как мы можем попасть в очередную клетку? Всё очевидно! Мы можем прийти в неё либо с верхней, либо с левой клетки. Answer[i][j] = Answer[i - 1][j] + Answer[i][j - 1]

Данную задачу можно решить также с помощью комбинаторики: Данную задачу можно решить также с помощью комбинаторики:

Б) Пусть в каждой клетке поля записано некоторое число. Требуется найти максимальную сумму чисел, которую можно набрать по пути в правый нижний угол. Б) Пусть в каждой клетке поля записано некоторое число. Требуется найти максимальную сумму чисел, которую можно набрать по пути в правый нижний угол.

Пусть А[i][j] – число в (i,j) клетке, а dp[i][j] ответ для неё. Пусть А[i][j] – число в (i,j) клетке, а dp[i][j] ответ для неё. dp[1][1] = A[1][1]; dp[1][j] = , dp[i][1]= 3) dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + A[i][j];

В результате получим такую таблицу:

Последовательность из нулей и единиц без двух единиц подряд. Дано число N. Рассмотрим все последовательностей из нулей и единиц. Назовём последовательность хорошей, если в ней нигде не встречается две единицы подряд. Требуется посчитать общее количество хороших последовательностей.

dp[i][j] – ответ для последовательности длины i, оканчивающейся на j dp[i][j] – ответ для последовательности длины i, оканчивающейся на j dp[1][0] = dp[1][1] = 1; dp[i][0] = dp[i - 1][0] + dp[1 - 1][1]; dp[i][1] = dp[i - 1][1]; А можно заметить, что это числа Фибоначчи 

Немного теории Определения: Состояние – это набор параметров, с помощью которых мы фиксируем подзадачу Переходы – это рекуррентное соотношение между состояниями Порядок пересчёта – это порядок, по которому мы обходим состояния

Чтобы успешно решить задачу динамикой нужно ответить на следующие вопросы: Чтобы успешно решить задачу динамикой нужно ответить на следующие вопросы: 1) Что мы вычисляем? 2) Какие у нас состояния? 3) Каковы значения в начальных состояниях? 4) Какие переходы между состояниями? 5) Каков порядок пересчёта? 6) Где хранится ответ на задачу?

Порядок пересчёта Существует три порядка пересчёта: Прямой Состояния последовательно пересчитываются исходя из уже посчитанных.

2) Обратный 2) Обратный Обновляются все состояния, зависящие от текущего состояния

3) Ленивая динамика 3) Ленивая динамика Рекурсивная функция пересчёта динамики. Это что-то вроде поиска в глубину по ацикличному графу состояний, где рёбра – это зависимости между ними.

Классы задач на ДП Подсчёт объектов, в том числе определение существования объекта. Т.е. надо посчитать, сколько всего существует объектов с заданными свойствами, или проверить, существует ли хотя бы один. Нахождение оптимального объекта. Требуется в некотором множестве объектов найти в некотором смысле оптимальный. Вывод k-ого объекта. Нужно найти в некотором порядке k-ый объект.

Виды задач на ДП Линейное ДП Многомерное ДП ДП на подотрезках ДП по полной сумме ДП на ациклических графах ДП на деревьях Игры(ретро-анализ) ДП на подмножествах. ДП по профилю Динамика по изломанному профилю

Отдельно рассмотрим семейство задач о рюкзаке Классическая постановка задачи: Есть N предметов, обладающих весом и стоимостью . В рюкзак влезают предметы, суммарный вес которых не превосходит W. Какую максимальную ценность может иметь рюкзак?

Перебирать все подмножества набора из N предметов. Сложность такого решения O(). Перебирать все подмножества набора из N предметов. Сложность такого решения O(). Метод динамического программирования. Сложность – O().

Решение методом динамического программирования Пусть dp[i][j] – есть максимальная стоимость предметов , которое можно уложить в рюкзак вместимости j, если мы используем только первые i предметов. dp[i][0] = dp[0][j] = 0; dp[i][j] = max(dp[i-1][j], dp[i-1][j - wi] + pi); Ответ: dp[N][W];

Пример W = 13, N = 5 w1 = 3, p1 = 1 w2 = 4, p2 = 6 w3 = 5, p3 = 4 w4 = 8, p4 = 7 w5 = 9, p5 = 6

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

Решение методом ДП Пусть dp[i][j] – максимальная стоимость любого возможного числа предметов типов от 1 до i, суммарным весом до j. dp[0][j] = dp[i][0] = 0; dp[i][j] = max(dp[i-1][j], dp[i-1][j-l*wi]+l*pi), где l Ответ: dp[N][W] Сложность: O()

Неограниченный рюкзак - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз. Неограниченный рюкзак - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз. Пример: Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму. Варианты решения: Перебор. Методом динамического программирования.

Пусть dp[i][j] – есть максимальная стоимость предметов , которое можно уложить в рюкзак вместимости j, если мы используем только первые i предметов. Пусть dp[i][j] – есть максимальная стоимость предметов , которое можно уложить в рюкзак вместимости j, если мы используем только первые i предметов. dp[i][0] = dp[0][j] = 0; dp[i][j] = max(dp[i-1][j], dp[i][j - wi] + pi); Ответ: dp[N][W];

Непрерывный рюкзак - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется. Непрерывный рюкзак - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется. Пример: Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму. Варианты решения: Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

Мультипликативный рюкзак – есть N предметов и M рюкзаков (M ≤ N). У каждого рюкзака своя вместимость . Задача: выбрать M не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость. Мультипликативный рюкзак – есть N предметов и M рюкзаков (M ≤ N). У каждого рюкзака своя вместимость . Задача: выбрать M не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость. Пример: У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно. Варианты решения: Перебор

Полезные ссылки goo.gl/Ip0tXp – Подробная лекция о динамическом программировании goo.gl/ehm0lw – Задача о рюкзаке