Неделя 10

Лекция 10. Задача о рюкзаке 0/1: крах жадных эвристик, двумерная таблица $dp[i][w]$, восстановление набора предметов, псевдополиномиальное время $\Theta(n W)$, оптимизация памяти до $\Theta(W)$ через обратный цикл, вариации (Subset Sum).

Семинар 10. Практика по одномерному ДП (материал лекции 9a): Фибоначчи, кузнечик с ценами и ловушками, восстановление траектории через массив prev, размен монет, House Robber. Зачёт по контесту на algo.ai.msu.ru.