- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему Динамическое программирование
Содержание
- 2. Рейтинг за домашнюю работу
- 3. Динамическое программирование — это когда у нас
- 4. Задача про черепашкуЕсть клетчатое поле NхM. В
- 5. Первая основная идея ДПБудем искать ответ не
- 6. А что дальше?Ответ для верхнего левого угла
- 7. Вторая основная идея ДПРешая задачу для очередной
- 8. А как мы можем попасть в очередную
- 9.
- 10. Б) Пусть в каждой клетке поля записано
- 11.
- 12. В результате получим такую таблицу:
- 13. Последовательность из нулей и единиц без двух единиц подряд.
- 14. dp[i][j] – ответ для последовательности длины i,
- 15. Немного теорииОпределения:Состояние – это набор параметров, с
- 16. Чтобы успешно решить задачу динамикой нужно ответить
- 17. Порядок пересчётаСуществует три порядка пересчёта:ПрямойСостояния последовательно пересчитываются исходя из уже посчитанных.
- 18. 2) ОбратныйОбновляются все состояния, зависящие от текущего состояния
- 19. 3) Ленивая динамикаРекурсивная функция пересчёта динамики. Это
- 20. Классы задач на ДППодсчёт объектов, в том
- 21. Виды задач на ДПЛинейное ДПМногомерное ДПДП на
- 22. Отдельно рассмотрим семейство задач о рюкзаке
- 23.
- 24. Решение методом динамического программированияПусть dp[i][j] – есть
- 25. ПримерW = 13, N = 5w1 =
- 26. Другие задачи семействаОграниченный рюкзак - обобщение классической
- 27. Решение методом ДП
- 28. Неограниченный рюкзак - обобщение ограниченного рюкзака, в
- 29. Пусть dp[i][j] – есть максимальная стоимость предметов
- 30. Непрерывный рюкзак - вариант задачи, в котором
- 31.
- 32. Скачать презентацию
- 33. Похожие презентации
Рейтинг за домашнюю работу
![dp[i][j] – ответ для последовательности длины i, оканчивающейся на jdp[1][0] = dp[1][1]](/img/tmb/15/1429962/807fe30756a4b621ef391e4bf5588d70-720x.jpg "Динамическое программирование")
![Решение методом динамического программированияПусть dp[i][j] – есть максимальная стоимость предметов , которое](/img/tmb/15/1429962/86f47e826cdfb2e691bb688495cf6eba-720x.jpg "Динамическое программирование")
![Пусть dp[i][j] – есть максимальная стоимость предметов , которое можно уложить в](/img/tmb/15/1429962/f9fc92554b5f0dec76d00f99a63d58ad-720x.jpg "Динамическое программирование")
Слайд 4
Задача про черепашку
Есть клетчатое поле NхM. В левом
верхнем углу сидит черепашка. Она умеет ходить только вправо
или вниз.А) Сколько у неё разных путей до правого нижнего угла?
Слайд 5
Первая основная идея ДП
Будем искать ответ не только
на нашу общую задачу, но и на более мелкие
аналогичные задачи («подзадача»). В нашем случае решим для каждой клетки поля сколькими способами до неё можно добраться.
Слайд 6
А что дальше?
Ответ для верхнего левого угла очевиден.
У нас только один способ до него добраться.
Для клеток
левого столбца и верхней строки тоже всё очевидно.
Слайд 7
Вторая основная идея ДП
Решая задачу для очередной клетки,
будем считать, что мы уже знаем ответ для предыдущих
клеток и попробуем, используя это знание, найти ответ для текущей.
Слайд 8
А как мы можем попасть в очередную клетку?
Всё
очевидно! Мы можем прийти в неё либо с верхней,
либо с левой клетки.Answer[i][j] = Answer[i - 1][j] + Answer[i][j - 1]
Слайд 10 Б) Пусть в каждой клетке поля записано некоторое
число. Требуется найти максимальную сумму чисел, которую можно набрать
по пути в правый нижний угол.Слайд 14 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];
А можно заметить, что это числа Фибоначчи ☺
Слайд 15
Немного теории
Определения:
Состояние – это набор параметров, с помощью
которых мы фиксируем подзадачу
Переходы – это рекуррентное соотношение между
состояниямиПорядок пересчёта – это порядок, по которому мы обходим состояния
Слайд 16 Чтобы успешно решить задачу динамикой нужно ответить на
следующие вопросы:
1) Что мы вычисляем?
2) Какие у нас состояния?
3)
Каковы значения в начальных состояниях?4) Какие переходы между состояниями?
5) Каков порядок пересчёта?
6) Где хранится ответ на задачу?
Слайд 17
Порядок пересчёта
Существует три порядка пересчёта:
Прямой
Состояния последовательно пересчитываются исходя
из уже посчитанных.
Слайд 19
3) Ленивая динамика
Рекурсивная функция пересчёта динамики. Это что-то
вроде поиска в глубину по ацикличному графу состояний, где
рёбра – это зависимости между ними.
Слайд 20
Классы задач на ДП
Подсчёт объектов, в том числе
определение существования объекта. Т.е. надо посчитать, сколько всего существует
объектов с заданными свойствами, или проверить, существует ли хотя бы один.Нахождение оптимального объекта. Требуется в некотором множестве объектов найти в некотором смысле оптимальный.
Вывод k-ого объекта. Нужно найти в некотором порядке k-ый объект.
Слайд 21
Виды задач на ДП
Линейное ДП
Многомерное ДП
ДП на подотрезках
ДП
по полной сумме
ДП на ациклических графах
ДП на деревьях
Игры(ретро-анализ)
ДП на
подмножествах.ДП по профилю
Динамика по изломанному профилю
Слайд 24
Решение методом динамического программирования
Пусть 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];
Слайд 26
Другие задачи семейства
Ограниченный рюкзак - обобщение классической задачи,
когда любой предмет может быть взят некоторое количество раз.
Пример: Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
Варианты решения:
Перебор.
Методом динамического программирования.
Слайд 28 Неограниченный рюкзак - обобщение ограниченного рюкзака, в котором
любой предмет может быть выбран любое количество раз.
Пример:
Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму. Варианты решения:
Перебор.
Методом динамического программирования.
Слайд 29 Пусть 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];
Слайд 30 Непрерывный рюкзак - вариант задачи, в котором возможно
брать любою дробную часть от предмета, при этом удельная
стоимость сохраняется.Пример: Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
Варианты решения:
Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.
