Семинар 4. Динамическое программирование (продолжение)
Пятница, 01 октября 2021
НГУ, ауд. 3122, НГУ, новый корпус
Динамическое программирование вперёд. Граф зависимостей.
Процесс построения/перебора решения. Как получить по процессу решение динамическим программированием: шаги, остановка, важная информация. Параметры динамики, внесение параметра в целевую функцию. Уменьшение затрачиваемой памяти для динамики по слоям.
Примеры построения динамики для наибольшей возрастающей подпоследовательности:
Примеры построения динамики для задачи о рюкзаке:
Решение задачи 8. Букет. Параметры динамики, если перебирать предметы. Параметры, если добавить сортировку. Решение за O(N S) времени и O(S) памяти.