Презентация Динамическое программирование. Примеры задач онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Динамическое программирование. Примеры задач абсолютно бесплатно. Урок-презентация на эту тему содержит всего 46 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Динамическое программирование. Примеры задач
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:46 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:803.00 kB
- Просмотров:56
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№3 слайд
![Признаки возможности](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img2.jpg)
Содержание слайда: Признаки возможности применения ДП
Возможность разбиения задачи на подзадачи (метод «разделяй-и-властвуй»)
Наличие свойства оптимальности для подзадач – оптимальный ответ для большой задачи строится на основе оптимальных ответов для меньших
Наличие перекрывающихся подзадач
№4 слайд
![Этапы решения задачи методом](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img3.jpg)
Содержание слайда: Этапы решения задачи методом динамического программирования
Разбиение задачи на подзадачи
Построение рекуррентной формулы для вычисления значения функции (включая начальные условия)
Вычисление значения функции для всех подзадач (важен порядок вычисления)
Восстановление структуры оптимального ответа
№7 слайд
![Разбиение на подзадачи Идея](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img6.jpg)
Содержание слайда: Разбиение на подзадачи
Идея: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai
Попробуйте построить рекуррентную формулу
Более точно: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai, последний элемент в которой - ai
№21 слайд
![Вычисление с сохранением](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img20.jpg)
Содержание слайда: Вычисление с сохранением информации для восстановления ответа
d[0] := 0;
prev[0] := -1;
for i := 1 to n do begin
max := 0;
bestj := -1;
for j := 1 to i – 1 do begin
if (a[j] < a[i]) and
(d[j] > max) then begin
max := d[j];
bestj := j;
end;
end;
d[i] := max + 1;
prev[i] := bestj;
end;
№27 слайд
![Вычисление d i Находим место](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img26.jpg)
Содержание слайда: Вычисление d[i]
Находим место в массиве last, на которое следует поставить a[i] – такую позицию j, что last[j-1] < a[i] ≤ last[j]
Это означает, что максимальная длина подпоследовательности, которая заканчивается в a[i] есть j (d[i] = j)
Позицию j надо искать с помощью двоичного поиска
Время работы алгоритма – O(nlogn)
№34 слайд
![Динамика вперед for i to n do](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img33.jpg)
Содержание слайда: «Динамика вперед»
for i := 0 to n do begin
for j := 0 to W do begin
c[i][j] := -INF;
end;
end;
for i := 0 to n – 1 do begin
for j := 0 to W do begin
if (c[i][j] = -INF) then continue;
c[i+1][j]:=max(c[i][j], c[i+1][j]);
if (j + w[i + 1] <= W) then begin
c[i + 1][j + w[i + 1]] = max(c[i][j] + p[i+1],
c[i + 1][j + w[i + 1]]);
end;
end;
end;
№37 слайд
![Упражнения Решите задачу о](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img36.jpg)
Содержание слайда: Упражнения
Решите задачу о рюкзаке для случая, когда имеется неограниченное число предметов каждого типа
Решите задачу о рюкзаке для случая, когда предметы можно брать не полностью (не золотые слитки, а золотой песок)
Решите смешанную задачу о рюкзаке – часть предметов можно брать только полностью, а остальные – можно и не полностью
№38 слайд
![Оптимальная триангуляция](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img37.jpg)
Содержание слайда: Оптимальная триангуляция многоугольника
Задан выпуклый многоугольник
Необходимо разбить его на треугольники, проведя несколько диагоналей
Суммарный периметр треугольников должен быть как можно меньшим
Кстати, сколько придется провести диагоналей, если в многоугольнике N углов?
№41 слайд
![Строение оптимального решения](/documents_6/f468e75c1f5eadc3cbe8192a7051137a/img40.jpg)
Содержание слайда: Строение оптимального решения
Рассмотрим оптимальную триангуляцию заданного (n+1)-угольника v0,v1, …, vn
Ребро v0vn входит в некоторый треугольник
Пусть это треугольник v0vnvk
Тогда стоимость триангуляции равна
Стоимость этого треугольника +
Стоимость триангуляции v0, v1, …, vk +
Стоимость триангуляции vk, vk+1, …, vn
Скачать все slide презентации Динамическое программирование. Примеры задач одним архивом:
Похожие презентации
-
Олимпиадные задачи. Динамическое программирование
-
Решение простейших задач линейного программирования графическим методом
-
«Решение задач на языке программирования» (Подготовка к ОГЭ)
-
Линейное программирование. Транспортная задача
-
Особенности применения задач линейного программирования при моделировании процессов функционирования сложных систем. Раздел 3
-
Динамическое программирование. Лекция 20
-
Система программирования PascalABC. NET и электронный задачник Programming Taskbook
-
Программирование на языке PascalABC. Решение задач. Обмен значений
-
Примеры программирования базовых алгоритмов циклических вычислительных процессов (ЦВП)
-
Язык программирования Паскаль. Решение задач