Изменения
Нет описания правки
# Будем говорить, что строки a и b образуют пару подстрок строки c, если c можно представить как xaybz, где x, y и z - произвольные строки. Решите с помощью ДП задачу о наибольшей общей паре подстрок.
# Задача о редакционном расстоянии: найдите последовательность действий для превращения строки $s$ в строку $t$ с помощью операций вставки, удаления и замены символа. Длины строк $m$ и $n$, соответственно. Требуется решить задачу за $O(mn)$ с памятью $O(m + n)$.
# Решите задачу о редакционном расстоянии, если помимо операций вставки, удаления и замены символа можно использовать операцию обмена местами двух соседних символов. Стоимость всех операций одинаковая.# Решите битоническую задачу о комивояжере: найдите во взвешенном графе гамильтонов цикл минимального веса, который удовлетворяет дополнительно следующему свойству: сначала номера посещенных вершин возрастают, а затем убывают. Время $O(n^2)$.
# Задача о рюкзаке: дано $n$ предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Решите задачу за время $O(nc)$ с памятью $O(c)$.
# Задача о рюкзаке без ограничения на число одинаковых предметов: дано $n$ типов предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Каждого предмета можно брать несколько (любое количество) экземпляров. Решите задачу за время $O(nc)$ с памятью $O(c)$.
