Меню

Динамическое программирование рюкзак НВП НОП

Динамическое программирование — рюкзак, НВП, НОП

Предполагается, что вы уже знакомы с базовыми понятиями динамического программирования и помните бинарный поиск.

  • Задача о рюкзаке
  • НВП
  • НОП
  • Динамика по префиксу и значению последнего элемента
  • Ленивая динамика

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

0-1 Рюкзак

В самой простой форме задача о рюкзаке формулируется так: > Даны \(n\) предметов с весами \(a_1,\ldots,a_n\) . Определите, на какой максимальный вес можно набрать предметов в рюкзак вместимости \(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 веса, рассмотрев 0 предметов.

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

0-1 Рюкзак со стоимостями

Немного усложним задачу. Пусть, теперь предметы имеют не только веса, но и стоимости \(c_1,\ldots,c_n\) . Соответственно, надо набрать предметов с наибольшей суммарной стоимостью, но весом не превосходящим \(W\) . Теперь в \(dp[i][j]\) будем хранить не просто возможно ли получить из первых \(i\) предметов набор веса \(j\) , а максимальную суммарную стоимость такого набора. Если же такой набор получить невозможно, то по-прежнему \(dp[i][j]=0\) . Переходы такие же как и в прошлой задаче. Изначально \(dp\) заполнено 0, так как для любого непустого набора мы пока не знаем, как его получить, а путой набор имеет стоимость 0.

Ответом на задачу будет максимальное \(dp[n][j]\) . Такое решение тоже работает за \(O(nW)\) .

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

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

Пусть, теперь предметов каждого типа может быть несколько, то есть даны не только веса и стоимости, но и максимальные количества каждого из предметов \(k_1,\ldots,k_n\) . Тогда для каждого состояния \(dp[i][j]\) переберем, сколько мы взяли предметов такого типа и сделаем переход из каждого соответствующего состояния. Понятно, что мы не сможем взять более, чем \(\lfloor\frac\rfloor\) предметов каждого типа.

Такое решение работает за \(O(nW^2)\) , так как \(k_i\) могут быть очень большими, а \(a_1=1\) .

Можете попробовать решить эту задачу за \(O(nW\log K)\) , где \(K\) — максимальное из \(k_i\) .

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

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

Такое решение работает за \(O(nW)\) .

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

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

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

  • первый способ — это построить массив prev, где для каждой ячейки \(dp[i][j]\) хранить, берем мы предмет i, или не берем предмет \(i\) .
  • второй способ — это определять это на ходу, смотря, какое из значений \(dp[i — 1][j]\) или \(dp[i — 1][j — a[i]] + c[i]\) больше.

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

Пусть, дана последовательность из \(n\) чисел \(a_1,\ldots,a_n\) . Требуется найти длину ее наибольшей возрастающей подпоследовательности (НВП), то есть длину такой наибольшей последовательности индексов \(i_1 , что \(a[i_1].

Пример: в последовательности \(100, \underline<20>, \underline<75>, 0, -40, \underline<80>, -10, \underline<120>, 110\) наибольшей возрастающей подпоследовательность является \(20, 75, 80, 120\) : она имеет длину \(4\) . Возрастающих подпоследовательностей длины 5 здесь нет.

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

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

\(dp[0] = 0\) . Но как найти формулу, выражающую \(dp[i]\) через предыдущин значения?

Ну, есть два варианта: * \(i\) -ое число не входит в НВП. Тогда \(dp[i] = 1\) * \(i\) -ое число входит в НВП. Тогда \(dp[i] = 1 + dp[k]\) , где \(k\) — индекс предыдущего числа в этой НВП. Так давайте просто его переберем. При этом надо учесть, что \(a[k]\) должно быть меньше, чем \(a[i]\) !

Итогвоая формула получается такая:

\[dp[i] = \max(1, 1 + \max\limits_

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

Читайте также:  Традиционная индустриальная постиндустриальная общество таблица капитал

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

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

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

Изначально \(min\_end[0]=-\infty, min\_end[i]=\infty\) для \(i>0\) . В качестве \(\infty\) надо выбрать число, которое заведомо больше любого из \(a_i\) , аналогично с \(-\infty\) .

Рассматривая очередной элемент, попробуем продлить им каждую подпоследовательность:

Ответом будет максимальный такой индекс \(j\) , что \(min\_end[j] \neq 0\) . Это решение работает за \(O(n^2)\) .

Его можно значительно ускорить, заметив два факта: — На любом шаге \(min\_end[i-1]\leq min\_end[i]\) . Это легко доказать от противного. — Из предыдущего факта следует, что любое \(a[i]\) обновит максимум одно значение динамики, так как попадет максимум в один интервал.

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

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

Даны две последовательности \(a_1,\ldots,a_n\) и \(b_1,\ldots,b_m\) . Требуется найти длину их наибольшей общей подпоследовательности (НОП), то есть длину наибольшей таких последовательностей \(i_1 и \(j_1 , что \(a[i_1]=b[j_1],\ldots,a[i_k]=b[j_k]\) .

Решим эту задачу с помощью динамического программирования, где \(dp[i][j]\) будет обозначать длину НОП, если мы рассмотрели префиксы последовательностей длины \(i\) и \(j\) .

Тогда заметим, что есть две ситуации, когда мы считаем \(dp[i][j]\) : * \(a_i \neq b_j\) , тогда хотя бы один из этиз символов не содержится в НОП, иначе она заканчивается на два разных символа. В этом случае \(dp[i][j] = max(dp[i — 1][j], dp[i][j — 1])\) * \(a_i = b_j\) , тогда несложно доказать, что точно есть максимальная НОП, в которую входят ОБА этих символа, а значит \(dp[i][j] = 1 + dp[i — 1][j — 1]\) .

А на пустых префиксах ответ 0.

Ответом является максимальное число в массиве \(dp\) . Решение работает за \(O(nm)\) .

Ответ при это восстанавливается классическим способом — с конца. Нам все еще нужно просто в каждой ячейке смотреть — если символы в ней равны, то нужно уменьшить \(i\) и \(j\) , иначе только один из них — так, чтобы НОП был максимален.

Задание

Сведите задачу НВП к задаче НОП.

Задание

Найдите НОП двух перестановок длины \(n\) за \(O(n\log n)\) .

Динамика по префиксу и значению последнего элемента

Пусть, дана последовательность \(a_1,\ldots,a_n\) , с максимальным значением \(A\) . Требуется найти длину наибольшей такой подпоследовательности, что ее элементы отличаются на более, чем на 1. Воспользуемся динамическим программированием, где \(dp[j]\) будет обозначать ответ с последним взятым элементом, равным \(j\) . Будем обновлять и хранить актуалььным весь массив \(dp\) целиком, проходясь по массиву \(a\) слева направо.

Соответственно для каждого \(i\) переходы можно делать только из таких \(j\) , что \(|a[i]-j|\leq 1\) .

Это решение за \(O(n + A)\) .

Заметим, что вот эти две идеи встречаются в задачах наиболее часто: * хранить в \(dp[i]\) ответ для \(i\) -ого префикса. Как в рюкзаке (где можно пользоваться \(i\) первыми предметами), НВП(где ответ на префиксе длины \(i\) ) и НОП (где ответ для префиксов длины \(i\) и \(j\) ). * хранить в \(dp[i]\) ответ для последовательностей, заканчивающихся на \(i\) .

Ленивая динамика

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

Решим, например, обычную задачу о рюкзаке таким образом. Изначально все \(dp[i][j]=-1\) , это будет обозначать, что значение еще не посчитано, кроме \(dp[0][j]=0\) .

Время работы так же составит \(O(nW)\) , так как каждое значение мы считаем только один раз, но истинное время работы будет в несколько раз больше, потому что константа на вызовы функции значительно выше чем на простой цикл.

Задание

Решите как можно больше задач из этих двух контестов:

Источник

Динамическое программирование — это просто. Решаем задачу о рюкзаке

Объясняем на пальцах, как использовать приёмы динамического программирования в жизни и на работе.

Вам никогда не хотелось бросить всё и уйти из дома с одним рюкзаком? Мне да, но институт, экзамены, сессия родственники, ипотека, кот — так что не вариант.

Но если бы я собирала такой рюкзак, то положила бы в него вещи, которые можно продать побыстрее и подороже, — чтобы выручить денег для новой жизни в новом месте.

Обозначим задачу

У нас есть довольно вместительный рюкзак и дорогие вещи, которые можно в него положить. Но вот беда — лямки рюкзака выдерживают, скажем, четыре килограмма, не больше.

  • из ноутбука, который весит три килограмма и стоит 2 000 долларов;
  • бензопилы (ею ещё можно отмахиваться от назойливых попутчиков) — четыре килограмма мощи, которые обойдутся новому владельцу в 3 000 долларов;
  • и мини- гитары — весит килограмм, а продать её можно за 1 500 долларов.

Нам нужно выбрать вещи наибольшей общей стоимости и не забывать про хилые лямки рюкзака.

Фулстек-разработчик. Любимый стек: Java + Angular, но в хорошей компании готова писать хоть на языке Ада.

Решаем вручную

Самый очевидный выход

Это полный перебор, конечно! Из трёх предметов можно составить всего восемь комбинаций. Подсчитаем стоимость для каждой и выберем самый выгодный вариант:

Пока предметов только три — вполне себе годное решение, но добавим ещё один — и вариантов станет 16, а для пяти их будет уже 32.

С добавлением каждого нового предмета число комбинаций удваивается, так что сложность такого алгоритма — O(2 n ). Это медленный способ.

Приблизительное решение

Применим так называемый жадный алгоритм: на каждом шаге добавляем в рюкзак самый дорогой предмет, пока лимит веса не превышен.

В случае с нашими предметами — одним шагом дело бы и закончилось. Мы сразу же взяли бы бензопилу за 3 000 долларов, потому что она самая дорогая. А при добавлении любого нового предмета в рюкзаке уже был бы перевес.

Было ли наше решение оптимальным? Нет, потому что гитару на пару с ноутбуком наш рюкзак тоже выдержит, но стоят они 1 500 долларов + 2 000 долларов = 3 500 долларов, что больше 3 000 долларов.

Оптимальное решение

Воспользуемся приёмами динамического программирования. Разобьём задачу на подзадачи и будем последовательно их решать. При этом на каждом следующем шаге используем результаты предыдущего.

Наглядно это можно представить в виде таблицы. Её ещё называют таблицей мемоизации. Столбцы нашей соответствуют килограммам (от одного до четырёх), а строки — предметам (гитара, бензопила, ноутбук).

1кг 2кг 3кг 4кг
гитара
бензопила
ноутбук

Таблица до заполнения

На пересечении, в ячейках, будем записывать общую стоимость предметов в рюкзаке.

Для каждого столбца (та или иная грузоподъёмность рюкзака) нужно решить: класть гитару в рюкзак или нет.

Так как гитара весит всего один килограмм, то она влезет уже на первом шаге. Поэтому в каждой ячейке первой строки напишем 1 500 — стоимость гитары.

Мы заполнили строку целиком и узнали, что промежуточный максимум для рюкзака в четыре килограмма составляет 1500 долларов.

1кг 2кг 3кг 4кг
гитара 1500 1500 1500 1500
бензопила
ноутбук

Таблица для первого предмета — гитары

На следующем этапе рассматриваем двух кандидатов — гитару и бензопилу.

В рюкзаки, рассчитанные на один, два или три килограмма, бензопилу не положить, так что оставляем там гитару и максимум стоимости вещей 1 500 долларов. А вот для случая «четыре килограмма» обновляем максимум: кладём бензопилу стоимостью 3 000 долларов.

1кг 2кг 3кг 4кг
гитара 1500 1500 1500 1500
бензопила 1500 1500 1500 3000
ноутбук

Таблица для двух предметов — гитары и бензопилы

Добавим последний предмет — ноутбук.

Для первых двух столбцов ничего не меняется, так как ничего, кроме гитары, в рюкзаки с грузоподъёмностью один и два килограмма положить не получится.

Зато в трёхкилограммовый рюкзак уже можно вместо гитары положить ноутбук — он дороже, обновляем максимум в этом столбце до 2 000 долларов.

Интереснее всего ситуация в последней ячейке: мы можем положить ноутбук, но он весит всего три килограмма, ещё один килограмм остаётся свободным.

И вот тут, наконец, пригодятся промежуточные результаты: мы узнали на предыдущих шагах максимальную стоимость для рюкзака, который выдерживает один килограмм, — она равна 1 500 долларов.

В итоге получаем ноутбук + гитара = 3 500 долларов, это больше предыдущего максимума в 3 000 долларов. Так что ответ в задаче — 3 500 долларов.

1кг 2кг 3кг 4кг
гитара 1500 1500 1500 1500
бензопила 1500 1500 1500 3000
ноутбук 1500 1500 2000 3500

Таблица для всех трёх предметов

В общем случае формула для стоимости в каждой ячейке выглядит так:

S[i, j] = max (S[i−1, j], цена i-го предмета + S[i−1, j−вес i-го предмета]),

где i — номер строки, j — столбца.

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

Решим на Java

Определим класс для вещей, которые можно положить в рюкзак:

Источник



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

В общем виде задача о рюкзаке формулируется следующим способом: имеется рюкзак определенного объема и неограниченное количество предметов. Для каждого предмета известен его объем (вес) и ценность (стоимость, эффективность). В рюкзак можно положить целое число предметов различного типа. Цель состоит в том, чтобы суммарная ценность всех находящихся в рюкзаке предметов была максимальна, а их объем (вес) не превышал заданной величины. К подобной формулировке может быть сведена задача максимального использования грузоподъемности подвижного состава, грузовместимости судна, автомобиля и т.п. Такая задача часто возникает при выборе оптимального управления в экономико-финансовых областях (например распределение бюджета отдела по проектам).

Решение задачи в классической постановке

Подобные задачи легко решаются с помощью надстройки «Поиск решения». Подготовлены исходные данные (рисунок ниже). Задача состоит в том, чтобы за счет подбора значений ячеек B16:B19 добиться максимального значения целевой функции (значение ячейки D20).

рис.1

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

рис.2 рис.3

Модифицированная задача

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

На рисунке ниже показаны исходные данные модифицированного варианта задачи. В этом случае предполагается, что в рюкзак может быть положено не менее некоторого количества предметов.

рис.4

На следующем рисунке показаны ограничения на значения изменяемых ячеек B16:B19. В данном случае к ограничениям добавлено условие 16:19>=8:11, то есть задано минимальное необходимое количество предметов различных видов.

рис.5

Решение задачи представлено последнем рисунке.

рис.5

При необходимости дополнительное условие 16:19>=8:11 может быть изменено. Например, можно установить отдельные ограничения для всех предметов, назначив для некоторых из них точное количество предметов, в то время как для других — условие «не менее» или «не более»

Источник

Задача о рюкзаке: разбор решения на Python

Задача о рюкзаке на примере пиратского корабля

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

1. Подготовка

Предположим, у нас есть два массива. В одном содержатся значения веса всех предметов ( weights ), а в другом — их стоимость ( values ). Также нам дана грузоподъемность корабля ( cap ). Все достаточно просто. Давайте определим наш метод:

2. Стратегия

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

Исходя из этого, стратегия у нас будет такая:

  1. Отсортируем наш список предметов по их стоимости на единицу веса.
  2. Будем грузить на корабль самые ценные предметы, пока не достигнем предела грузоподъемности.

3. Создаем сортированный список предметов

Сначала мы создадим новый список items , где будут находиться элементы в отсортированном виде. Затем мы переберем в цикле список values (или weights — они все равно имеют одинаковую длину). Для каждого элемента мы будем сохранять его стоимость на единицу веса (value-per-item, vpw ), а также вес (зачем он нам нужен, увидите позже).

Далее нам нужно поместить этот элемент в список items . Но мы не можем просто добавить его в конец списка, ведь мы формируем список, отсортированный по vpw . Поэтому, чтобы определить, куда вставить элемент, мы будем обходить список items , сверяя каждый уже имеющийся там vpw с vpw текущего элемента.

Для начала, если список пока пуст, нам нечего сверять. Мы можем просто добавить наш элемент.

В противном случае мы обходим список. Мы не знаем точного числа переходов, которые придется совершить: будем идти по списку до тех пор, пока vpw нашего текущего элемента не окажется меньше, чем vpw элемента в списке. Тут отлично сработает цикл while.

Окей, теперь наш индекс k должен указывать на то место, куда нужно вставить новый элемент. Для вставки мы можем воспользоваться методом insert() .

4. Добавляем элементы из сортированного списка на «корабль»

Пришла пора наполнить корабль грузом. Как уже говорилось, мы собираемся перебирать список предметов, удобно отсортированных по убыванию стоимости, и добавлять эти предметы на корабль, пока не достигнем предела грузоподъемности.

Давайте создадим новые переменные. total — финальная стоимость груза, который удастся увезти на корабле (ее мы будем возвращать). Кроме того, мы создадим переменную cap_left для отслеживания, груз какого веса еще может принять корабль после добавления очередного предмета.

Теперь давайте переберем наши предметы.

По каждому элементу мы сначала будем проверять, поместится ли он целиком (по весу). Если да — добавляем его стоимость к total (стоимость можно найти путем умножения weight на vpw ). Не забудьте вычесть вес предмета из cap_left !

Предположим, мы добавили несколько предметов на корабль и еще осталось место, но его недостаточно для добавления следующего целого предмета. Но в условии сказано, предметы можно и делить на части.

Нам нужно проверить, осталось ли место, а затем высчитать, сколько нужно добавить к total . Тут используется математика: мы умножаем vpw элемента, который не помещается полностью, на остаток веса, который еще может принять корабль. После того как мы добавим результат к total , cap_left устанавливается в 0.

Нам остается лишь вернуть total ! Все вместе выглядит так:

5. Проверяем

Допустим, в нашей добыче есть три предмета: бочка рома, мешок муки и рулон шелка. Вместимость корабля — 60 фунтов.

У шелка самый высокий VPW — 4 монеты за фунт. Следующим идет ром (3) и мука (2). Шелк добавляем первым, затем ром. После этого корабль может принять еще 10 фунтов веса: их мы заполняем мукой. 10 фунтов муки стоят 20 монет. Таким образом, общая стоимость добра, которое мы можем увезти на корабле, — 200 монет.

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

Источник

Adblock
detector