Семинар 4. Динамическое программирование
Алгоритмы и структуры данных, часть 1


Что: Лекция
Когда: Суббота, 06 октября 2018, 16:20–17:55
Где: НГУ, ауд. 2128

Описание

Динамическое программирование вперёд. Граф зависимостей.

Процесс построения/перебора решения. Как получить по процессу решение динамическим программированием: шаги, остановка, важная информация. Параметры динамики, внесение параметра в целевую функцию. Уменьшение затрачиваемой памяти для динамики по слоям.

Примеры построения динамики для наибольшей возрастающей подпоследовательности:

  • на шаге выбираем следующий добавляемый элемент
  • на шаге решаем, добавлять или не добавлять элемент

Примеры построения динамики для задачи о рюкзаке:

  • на шаге решаем, брать или не брать предмет
  • как в 1, только можно добавлять балласт в любой момент
  • на шаге решаем, какой предмет взять следующим

Решение задачи 8. Букет. Параметры динамики, если перебирать предметы. Параметры, если добавить сортировку. Решение за O(N S) времени и O(S) памяти.

Видео