Динамическое программирование: решение задачи о рюкзаке

Алгоритмы в решении задач

Чтобы решать сложные задачи в математике, используются методы так называемого динамического программирования. Оно позволяет выделить подзадачи и решать их последовательно. Разберемся с основными принципами такого подхода на Python, решив популярную задачу о рюкзаке (задачу о ранце, knapsack problem).

Задача о рюкзаке

Рюкзак

Классическая задача о рюкзаке формулируется следующим образом.

Есть n разных вещей, которые весят a1,…,an. Необходимо определить максимальный возможный вес вещей, которые могут влезть в рюкзак объемом W.

Применим метод динамического программирования для поиска решения. Создадим матрицу dp[i][j] , где  i  — число рассмотренных вещей, а j  — суммарный вес, который мы уже набрали. Состояние dp[i][j]=True для возможной ситуации, иначе dp[i][j]=False.

Для любого возможного dp[i][j] есть два варианта: 

• рассмотреть предмет номер i, а потом рассчитать ответ по формуле dp[i−1][j−a[i]], 
• не брать предмет, обновив ответ из dp[i−1][j]. 

Можно набрать 0 веса, не рассматривая ни одного предмета.

Итак, мы инициализируем dp[0][0] = True и затем заполняем матрицу следующим образом:

dp[0][0] = True

for i in range(1, n + 1):

    for j in range(0, W + 1):

        dp[i][j] = dp[i - 1][j]

        if a[i] <= j and dp[i - 1][j - a[i]]:

            dp[i][j] = True

Ответ — максимальный вес j, для которого dp[n][j]=True. Таким образом, мы решаем задачу за время O(nW):

• n — число предметов,  
• W — вместимость рюкзака.

Рюкзак со стоимостями

Сложность задачи можно увеличить, учитывая стоимость предметов помимо их весов. Теперь требуется выбрать набор предметов с максимальной суммарной стоимостью, не превышающий заданный вес W. 

Для этого можно модифицировать массив dp[i][j]. Удерживаем в памяти не только информацию о возможности достичь веса j из набора в i предметов, но и максимальную суммарную стоимость такого набора. Если набор собрать нельзя, значение dp[i][j] нулевое. Изначальные значения dp тоже нулевые: пустой набор ничего не стоит, а как собрать какой-то другой, мы пока не знаем.

Затем мы используем два вложенных цикла:

for i in range(1, n + 1):

    for j in range(0, W + 1):

        dp[i][j] = dp[i - 1][j]

        if a[i] <= j:

            dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + c[i])

Обновляем dp[i][j] исходя из предыдущих данных. Ответ — максимальное значение dp[n][j]. Временная сложность такого решения составляет O(nW).

Если у вас веса предметов сильно превышают их стоимость, вы можете поменять их местами и решать задачу, минимизируя вес при заданной стоимости. Этот трюк с обменом значениями динамики и параметров является распространенным в динамическом программировании.

Рюкзак с ограниченным числом предметов

Добавим еще одно условие. Теперь есть ограничения на количество предметов каждого типа, обозначенные через k1,…,kn. Для решения этой задачи мы будем использовать динамическое программирование. Давайте рассмотрим глубокий пересмотр решения этой задачи с учетом новых условий.

Для каждого состояния dp[i][j] будем рассматривать количество взятых предметов каждого типа и делать переход из соответствующего состояния. Очевидно, что мы не можем взять больше ⌊Wai⌋ предметов каждого типа.

for i in range(1, n + 1):

    for j in range(0, W + 1):

        for cnt in range(min(k[i], W // a[i]) + 1):

            if a[i] * cnt <= j:

                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i] * cnt] + c[i] * cnt)

Это решение имеет сложность O(nW^2), так как ki могут быть очень большими, и a1 равно 1.

Вызов того, чтобы решить эту задачу за O(nWlogK), где K — максимальное из ki, предполагает использование другого подхода. Для этого мы можем использовать модифицированный метод динамического программирования, который позволит нам решить задачу с учетом этих ограничений в более эффективное время.

Рюкзак с неограниченным числом предметов

Представим, что у нас нет ограничений на количество конкретных предметов (ki не играют роли), а их количество фактически бесконечно. В этом случае задача о рюкзаке становится проще. Мы можем вернуться к стандартной задаче рюкзака с весами и стоимостями. Дополнительное условие заключается в том, что теперь мы можем обновлять значения прямо из текущей строки, а не только из предыдущей. Обратите внимание, что для каждого состояния достаточно рассмотреть взятие только одного предмета данного типа, поскольку взятие двух и более предметов будет рассмотрено одновременно.

for i in range(1, n + 1):

    for j in range(0, W + 1):

        dp[i][j] = dp[i - 1][j]

        if a[i] <= j:

            dp[i][j] = max(dp[i][j], dp[i][j - a[i]] + c[i])

Это решение имеет сложность O(nW).

Если W большое, а значения ai относительно малы, мы можем решить задачу за O(n+A^3), где A — максимальное из ai. Мы замечаем, что если W достаточно велико, то большая часть рюкзака будет заполнена предметами одного типа с максимальной удельной стоимостью. Мы можем показать, что один и тот же предмет будет занимать не менее W-A^2 веса. Таким образом, мы можем за O(n) выбрать предмет с максимальным удельным весом и затем запустить предыдущий алгоритм для оставшихся предметов, что выполнится за O(A^3), так как нам надо рассматривать не более A предметов с максимальным весом A^2.

Восстановление ответа

Во всех описанных задачах восстановление ответа осуществляется стандартным способом: необходимо пройти назад от финального результата до начального состояния.

Первый способ для восстановления ответа заключается в создании массива prev, где для каждой ячейки dp[i][j] мы храним информацию о том, берем ли мы предмет i или нет.

Второй способ включает принятие решения динамически, определяя, какое значение лучше: dp[i−1][j] или dp[i−1][j−a[i]]+c[i]. В зависимости от этого выбирается следующее состояние.

Наибольшая возрастающая подпоследовательность

Предположим, у нас есть последовательность из n чисел a1,…,an. Наша цель — найти длину наибольшей возрастающей подпоследовательности (НВП), то есть длину наибольшей последовательности индексов i1<i2<…<ik, таких, что a[i1]<a[i2]<…<a[ik].

Например, в последовательности 100, 20, 75, 0, -40, 80, -10, 120, 110, наибольшей возрастающей подпоследовательностью будет 20, 75, 80, 120, с длиной 4. Здесь нет возрастающих подпоследовательностей длины 5.

НВП за \(O(N^2)\)

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

Изначально устанавливаем dp[0]=0. Как нам выразить формулу для dp[i] через предыдущие значения?

Рассмотрим два варианта:

1. i-ое число не входит в НВП. Тогда dp[i]=1.

2. i-ое число входит в НВП. Тогда dp[i]=1+dp[k], где k - индекс предыдущего числа в этой НВП. Перебираем возможные k, учитывая условие a[k] < a[i].

Таким образом, итоговая формула выглядит следующим образом:

dp[i] = max(1, 1 + max(k | a[k] < a[i]dp[k])

Этот алгоритм работает с временной сложностью O(N^2): у нас N состояний динамики, и каждое из них рассчитывается за O(N) действий при поиске максимума.

Для восстановления ответа применяется тот же способ: для каждого состояния необходимо сохранить, где был достигнут максимум — это будет предыдущее число в НВП.

НВП за \(O(N\log{N})\)

Решим данную задачу с помощью более нестандартного подхода к динамическому программированию, где min_end[i] будет представлять собой минимальное число, на которое может заканчиваться наибольшая возрастающая подпоследовательность (НВП) длины i. Мы будем пошагово обрабатывать числа слева направо, при этом в массиве будет храниться информация только о всех НВП в уже обработанной части последовательности.

Изначально установим min_end[0] = -∞, min_end[i] = ∞ для i > 0. В качестве ∞ мы выберем число, которое гарантированно больше любого из чисел ai, аналогично для -∞.

При рассмотрении каждого элемента последовательности мы будем пытаться продлить каждую подпоследовательность:

n = 6

a = [6, 1, 5, 3, 4, 2] # НВП: 1, 3, 4

inf = 100

min_end = [-inf] + [inf] * n

for i in range(n):

    for j in range(n):

        if min_end[j - 1] < a[i] < min_end[j]:

            min_end[j] = a[i]

print(min_end)

Ответом на задачу будет максимальный индекс j, при котором min_end[j] ≠ 0. Это решение имеет временную сложность O(n^2).

Можно значительно ускорить алгоритм, обратив внимание на следующие факты:

1. На каждом шаге выполнения цикла: min_end[i-1] ≤ min_end[i]. Это утверждение легко доказать методом от противного.

2. Из предыдущего факта следует, что каждое число a[i] будет обновлять максимум один элемент массива min_end, так как оно может попасть максимум в один интервал.

Таким образом, для поиска индекса j, который будет обновлен числом a[i], мы можем воспользоваться бинарным поиском. Это ускоренное решение будет работать за время O (n log n).

Выводы

Для решениязадачи о рюкзаке подойдет программирование на разных языках: Python, Java, JavaScript. В быту ей тоже можно найти практическое применение. Например, вы собираетесь отдохнуть в другом городе и хотите посетить как можно больше интересных мест — их тоже можно представить в виде предметов разного «веса». Аналогичным образом можно оценивать рабочие, бытовые дела, их важность и затраты сил. Овладев азами динамического программирования, вы можете без труда строить планы в разных ситуациях.