Занятие 8

Практическое занятие 8: динамическое программирование на последовательностях¶

Цель: Получить практический навык реализации популярных алгоритмов динамического программирования на языке Python¶

Задачи:¶

Одномерное динамическое программирование: наилучший способ
Поиск подотрезка массива с максимальной/минимальной суммой
Длина наидлиннейшей возрастающей подпоследовательности
Длина набольшей по длине общей подпоследовательности
Алгоритм "укладки рюкзака" (с дискретными массами)

1. Одномерное динамическое программирование: наилучший способ¶

Динамическое программирование - это способ решения сложных задачс использованием сохраненных в памяти решений более простых задач того же типа.

В качестве примера задачи на нахождение наилучшего способа рассмотрим следующую задачу о кузнечике.

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость, различную для различных точек. Стоимость прыжка в точку i задается значением P[i] списка стоимостей P. Необходимо найти минимальную стоимость маршрута кузнечика из точки 1 в точку n (то есть, наилучшее решение в данном случае — это маршрут с минимальной стоимостью).

Пусть F(n) — минимальная стоимость пути из 1 в n. Выведем рекуррентное соотношение для F(n). Чтобы попасть в точку n мы должны попасть в точку n-1 или n-2. Минимальные стоимости этих маршрутов будут равны F(n-1) и F(n-2) соответственно. К ним необходимо добавить значение P[n] за прыжок в клетку n. При этом из двух клеток n-1 и n-2 нужно выбрать тот маршрут, который имеет наименьшую стоимость.

Получим соотношение для F(n): $$F(n) = min(F(n-1), F(n-2)) + P[n]$$

Вычислим значение целевой функции F(n) при помощи динамического программирования:

F = [0] * (n + 1) # значение F[0] не используется
F[1] = P[1]
for i in range(2, n + 1):
    F[i] = min(F[i - 1], F[i - 2]) + P[i]

После выполнения этого цикла в списке F будет записана минимальная стоимость маршрута для всех точек от 1 до n.

2. Поиск подотрезка массива с максимальной/минимальной суммой¶

2.1 Поиск подотрезка массива с максимальной суммой¶

Пусть дан массив чисел a длины n, требуется найти такой его отрезок a[l:r+1], что сумма в нем максимальна: $$\max_{1 \leq l \leq r \leq n}\sum_{i=l}^{r}a[i]$$ Для решения данной задачи рассмотрим алгоритм, предложенный Джеем Каданом (Jay Kadane) в 1984 г.

Сам алгоритм выглядит следующим образом. Будем идти по массиву и накапливать в некоторой переменной s текущую частичную сумму. Если в какой-то момент s окажется отрицательной, то присвоим s = 0. Максимум из всех значений переменной s, случившихся за время работы, и будет ответом на задачу:

res_sum = 0
current_sum = 0
for i in range(len(a)):
    current_sum += a[i]
    if current_sum < 0:
        current_sum = 0
    elif res_sum < current_sum:
        res_sum = current_sum

Задача 1 — выполните рассмотренный алгоритм для массива a = [-2, -3, 4, -1, 2, 5, -3]:

In [ ]:

Приведенный ниже код дополняет решением поиском границ массива с максимальной суммой:

res_sum = 0
current_sum = 0
index_l = 0
index_r = 0
index_minus = -1
for i in range(len(a)):
    current_sum += a[i]
    if current_sum < 0:
        current_sum = 0
        index_minus = i
    elif res_sum < current_sum:
        res_sum = current_sum
        index_r = i
        index_l = index_minus + 1

Задача 2 — выполните рассмотренный алгоритм для массива a = [-2, -3, 4, -1, 2, 5, -3]:

In [ ]:

2.2 Поиск подотрезка массива с минимальной суммой¶

Задача о поиске минимального подотрезка — та же самая задача, что поиск минимального подотрезка, достаточно лишь изменить знаки всех чисел на противоположные.

Убедитесь в этом для задач 1 и 2.

3. Длина наидлиннейшей возрастающей подпоследовательности¶

Рассмотрим числовую последовательность из n* элеметов $a_{0}, a_{1}, ..., a_{n-1}$. Рассмотрим задачу нахождения среди всех возможных подпоследовательностей данной последовательности монотонно возрастающей подпоследовательности наибольшей длины.

Обозначим через L(i) длину наибольшей возрастающей подпоследовательности, последним элементом которой будет элемент $a_i$. Тогда для вычисления значения L(i) рассмотрим предпоследний элемент этой последовательности. Пусть это элемент $a_j$, тогда $j < i$ и $a_{j} < a_{i}$. Длина наибольшей возрастающей подпоследовательности, заканчивающейся $a_j$ есть L(j), значит, необходимо найти такое подходящее $j$, что L(j) будет наибольшим. Итак, $L(i) = 1 + \max_{j < i, a_{j} < a_{i}}L(j)$. Если же ни одного такого подходящего $j$ нет, то L(i) = 1.

Соответствующая программа вычисления значений функции L будет выглядеть так:

L = [0] * len(a)
for i in range(len(a)):
    for j in range(i):
        if a[j] < a[i] and L[j] > L[i]:
            L[i] = L[j]
    L[i] += 1

Ответом (длиной наибольшей возрастающей подпоследовательности) будет наибольшее значение L(i).

Задача 3 — с помощью рассмотренного выше алгоритма найдите длину наибольшей возрастающей последовательности для списка a = [1, 3, 2, 5, 4]:

4. Длина набольшей по длине общей подпоследовательности¶

Рассмотрим две строки (или числовые последовательности) — A и B. Пусть первая строка состоит из n символов $a_{0},..., a_{n-1}$, вторая строка состоит из m символов $b_{0},..., b_{m-1}$. Подпоследовательностью данной строки (последовательности) называется некоторое подмножество символов исходной строки, следующих в том же порядке, в котором они идут в исходной строке, но не обязательно подряд. Пустая подпоследовательность не содержит ни одного элемента и также является подпоследовательностью любой строки.

Рассмотрим задачу — для двух данных строк найти такую строку наибольшей длины, которая была бы подпоследовательностью каждой из них. Например, если A = «abcabaac», B = «baccbca» то у строк A и B есть общая подпоследовательность длины 4, например, «acba» или «acbc».

Рассмотрим последние символы данных строк $a_{n-1}$ и $b_{m-1}$. Если эти символы совпадают, то они обязательно войдут последними символами и в наибольшую общую подпоследовательность данных строк. Тогда можно свести задачу нахождения наибольшей общей подпоследовательности для строк $a_{0},..., a_{n-1}$ и $b_{0},..., b_{m-1}$ к задаче нахождения наибольшей общей подпоследовательности для строк, полученных отбрасыванием от данных строк последнего символа, то есть для $a_{0},..., a_{n-2}$ и $b_{0},..., b_{m-2}$. Затем к ответу для «укороченных» строк добавим последние (равные) символы исходных строк ($a_{n-1}$ или $b_{m-1}$) и получим ответ для исходных строк.

Если же последние символы исходных строк не совпадают, то эти символы ($a_{n-1}$ и $b_{m-1}$) не могут одновременно входить в наибольшую общую подпоследовательность, поэтому можно один из них отбросить. Тогда задача сводится к нахождению наибольшей общей подпоследовательности для одного из двух случаев - для строк $a_{0},..., a_{n-2}$ и $b_{0},..., b_{m-1}$ или для строк $a_{0},..., a_{n-1}$ и $b_{0},..., b_{m-2}$.

Мы научились сводить задачу нахождения наибольшей общей подпоследовательности двух строк к меньшей задаче - нахождения наибольшей общей подпоследовательности для строк, полученных отбрасыванием последних символов от исходных строк, то есть для префиксов исходных строк. Для дальнейшего решения задачи будем следовать принципу построения решения при помощи динамического программирования.

Рассмотрим префикс $A'$ первой строки из i символов: $A' = a_{0},..., a_{i-1}$ и префикс $B'$ второй строки из j символов: $B' = b_{0},..., b_{j-1}$. В терминах срезов языка Python можно считать, что $A' = A[:i]$ и $B' = B[:j]$. Обозначим через $F(i, j)$ длину наибольшей общей подпоследовательности для $A'$ и $B'$.

Теперь выпишем рекуррентные соотношения. Они зависят от того, совпадают ли последние символы рассматриваемых строк $A'$ и $B'$. Если $a_{i-1} = b_{j-1}$, то тогда $F(i, j) = F(i-1, j-1) + 1$ - нужно решить задачу для строк, полученных отбрасыванием последних символов рассматриваемых строк и добавить 1 символ к ответу. В противном случае нужно рассмотреть два случая: $F(i-1, j)$ и $F(i, j-1)$, которые соответствуют отбрасыванию по одному символу от конца каждой из рассматриваемых строк. В этом случае $F(i, j) = max(F(i-1, j), F(i, j-1))$.

Начальные значения функции F задаются просто: если одна из строк - пустая, то общая подпоследовательность также пустая, то есть имеет длину 0: $F(0, j) = F(i, 0) = 0$.

Далее необходимо завести двумерный массив размером $(n + 1) x (m + 1)$ и заполнить его значениями по указанным рекуррентным соотношениям. Сначала весь массив заполним нулями (что задаст граничные значения), затем двумя вложенными циклами по i и по j заполним оставшуюся часть массива:

n = len(A)
m = len(B)
F = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if A[i - 1] == B[j - 1]:
            F[i][j] = F[i - 1][j - 1] + 1 
        else: 
            F[i][j] = max(F[i - 1][j], F[i][j - 1]) 

print(F[n][m])

Задача 4 — С помощью рассмотренного выше алгоритма найдите дляну максимальной общей подпоследовательности для A = 'abcabaac' B = 'baccbca':

In [ ]:

5. Алгоритм "укладки рюкзака" (с дискретными массами)¶

В этой задаче имеется несколько предметов, для каждого предмета заданы две характеристики: вес $w_{i} > 0$ и стоимость («полезность») предмета $p_{i} > 0$. Необходимо выбрать множество предметов суммарной максимальной стоимости, при этом суммарная масса выбранных предметов должна быть ограничена значением K.

Если массы всех предметов являются целыми числами (так называемая «дискретная» задача), то задачу можно решить при помощи динамического программирования.

Будем для каждой возможной массы k хранить информацию о способе набора этой массы и наибольшую стоимость предметов, которые можно набрать в рюкзак данной массы.

Определим функцию $F(i, k)$ — максимальная стоимость предметов, которые можно уложить в рюкзак массы k, если можно использовать только первые i предметов.

Выведем рекуррентное соотношение для $F(i, k)$ уменьшив значение i. Есть две возможности собрать рюкзак, используя первые i предметов — взять предмет с номером i или не брать.

Если не брать предмет с номером i, то в этом случае $F(i, k) = F(i - 1, k)$, так как рюкзак массы k будет собран только с использованием первых i - 1 предмета.

Если же предмет с номером i войдет в рюкзак (это можно сделать только при $k \geq w_{i}$), то останется свободная вместимость рюкзака $k - w_{i}$, которую можно будет заполнить первыми i - 1 предметами, максимальная стоимость рюкзака в этом случае будет $F(i - 1, k - w_{i})$. Но поскольку предмет номер i был включен в рюкзак, то стоимость рюкзака увеличится на $p_{i}$. То есть в этом случае $F(i, k) = F(i - 1, k - w_{i}) + p_{i}$.

Из двух возможных вариантов нужно выбрать вариант наибольшей стоимости, то есть $F(i, k) = max(F(i - 1, k), F(i - 1, k - w_{i}) + p_{i})$.

Для хранения значения функции F будем использовать двумерный список. При этом массы предметов хранятся в списке W, их стоимости - в списке P. Будем считать (для простоты записи программы), что предметы пронумерованы от 1 до n:

F = [ [0] * (K + 1) for i in range(n + 1)]
for i in range(1, n + 1):
    for k in range(1, K + 1):
        if k >= W[i]:
            F[i][k] = max(F[i - 1][k], F[i - 1][k - W[i]] + P[i]) 
        else: 
            F[i][k] = F[i - 1][k]

In [ ]: