Содержание
- 2. Цель лекции Изучить еще несколько примеров задач, решаемых с помощью динамического программирования, и их решения
- 3. Признаки возможности применения ДП Возможность разбиения задачи на подзадачи (метод «разделяй-и-властвуй») Наличие свойства оптимальности для подзадач
- 4. Этапы решения задачи методом динамического программирования Разбиение задачи на подзадачи Построение рекуррентной формулы для вычисления значения
- 5. Наибольшая возрастающая подпоследовательность Задана последовательность чисел a1, a2, …, an Необходимо найти возрастающую подпоследовательность наибольшей длины
- 6. Перебор? Число различных подпоследовательностей: (2n – 1) Можно применять для n ≤ 20
- 7. Разбиение на подзадачи Идея: найти наибольшую возрастающую подпоследовательность среди первых i элементов: a1, a2, …, ai
- 8. Рекуррентная формула d[i] – длина наибольшей возрастающей подпоследовательности, которая заканчивается в ai Считается, что максимум равен
- 9. Начальные условия Можно сделать немного проще Считаем, что в начало добавлен a0=–∞, а d[0] = 0
- 10. Пример (1)
- 11. Пример (2)
- 12. Пример (3)
- 13. Пример (4)
- 14. Пример (5)
- 15. Пример (6)
- 16. Пример (7)
- 17. Пример (8)
- 18. Пример (9)
- 19. Программа d[0] := 0; for i := 1 to n do begin max := 0; for
- 20. Восстановление ответа Где находится длина L наибольшей возрастающей подпоследовательности? L := 0; pos := -1; for
- 21. Вычисление с сохранением информации для восстановления ответа d[0] := 0; prev[0] := -1; for i :=
- 22. Восстановление ответа procedure restore(i : integer); begin if (i > 0) then begin restore(prev[i]); write(a[i]); end;
- 23. Пример 1 3 4 10 15
- 24. Время работы Время работы этого алгоритма – O(n2) Можно ли быстрее?
- 25. Более быстрый алгоритм Похоже, что от вычисления d[i] никуда не деться Попробуем вычислять d[i] быстрее Пусть
- 26. Свойство массива last Этот массив является неубывающим Действительно, пусть i last[j] Из подпоследовательности длины i можно
- 27. Вычисление d[i] Находим место в массиве last, на которое следует поставить a[i] – такую позицию j,
- 28. Упражнения Продумать, как сохранять информацию для восстановления ответа Реализовать этот алгоритм
- 29. Задача о рюкзаке Есть рюкзак вместимостью W и n предметов, каждый из которых характеризуется ценностью pi
- 30. Разбиение на подзадачи Два параметра – число обработанных предметов и вместимость рюкзака c[i][j] – максимальная суммарная
- 31. Рекуррентная формула Очередной предмет можно либо взять, либо не взять
- 32. Начальные условия c[0][j] = 0 для j=0…W c[i][0] = 0 для i=0…n
- 33. Два способа реализации Метод заполнения таблицы можно реализовать двумя способами «Динамика назад» (этот метод использовался во
- 34. «Динамика вперед» for i := 0 to n do begin for j := 0 to W
- 35. Восстановление ответа Необходимо запоминать для каждого состояния (i, j) надо ли брать очередной предмет Реализуйте сами!
- 36. Время работы алгоритма Время работы этого алгоритма – O(nW) Таким образом, он применим только для относительно
- 37. Упражнения Решите задачу о рюкзаке для случая, когда имеется неограниченное число предметов каждого типа Решите задачу
- 38. Оптимальная триангуляция многоугольника Задан выпуклый многоугольник Необходимо разбить его на треугольники, проведя несколько диагоналей Суммарный периметр
- 39. Нумерация вершин многоугольника Вершины (n+1)-угольника нумеруются числами от 0 до n При этом когда говорится о
- 40. Разбиение на подзадачи После вырезания одного треугольника, многоугольника распадается на два, которые можно рассматривать отдельно
- 41. Строение оптимального решения Рассмотрим оптимальную триангуляцию заданного (n+1)-угольника v0,v1, …, vn Ребро v0vn входит в некоторый
- 42. Рекуррентная формула d[i][j] – минимальная стоимость триангуляции многоугольника vi-1…vj (1≤i Ответ находится в d[1][n] Начальные условия:
- 43. Восстановление ответа Для каждой подзадачи необходимо запомнить оптимальное значение числа k Реализуйте самостоятельно!
- 44. Упражнения Пусть стоимостью треугольника считается его площадь. Как найти оптимальную триангуляцию? Пусть необходимо минимизировать суммарную длину
- 45. Выводы Рассмотрены три примера задач, решаемых методом динамического программирования Метод заполнения таблицы может быть реализован двумя
- 47. Скачать презентацию