Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняГлава 14 алгоритмов и структур данныхСтатья также является третьей статьей на тему динамического программирования.
В предыдущих статьях мы представилиДвоичное разделение нескольких рюкзаковрешение. В большинстве случаев этого решения достаточно, но если вы столкнетесь с крайне проблемными людьми, вы все равно можете застрять. В настоящее время можно использовать только более быстрый метод — монотонную оптимизацию, которую мы сегодня рассмотрим.
Монотонная оптимизация — это сокращение от монотонной оптимизации очереди.Монотонный стекМы уже представили его в предыдущей теме LeetCode. Суть его в простом стеке.Выталкивая некоторые элементы вверху стека при вставке элементов, гарантируется порядок элементов в стеке. Монотонная очередь аналогична, но позиция вставки элемента другая. Стек можно вставить только с вершины стека, а очередь вставляется с конца очереди.
Например, давайте посмотрим на рисунок ниже.Рисунок ниже представляет собой типичную монотонную очередь.Элементы в очереди [10, 6, 3]. Голова очереди равна 10, и элементы в очереди уменьшаются от головы очереди к хвосту очереди.
Если мы в этот момент вставим 9 с конца очереди, так как 9 больше 3 в конце очереди, 3 вне очереди. Мы продолжаем судить и обнаруживаем, что 9 все еще больше 6, поэтому 6 снова вне очереди. Окончательный результат [10, 9]. Если быть точным, так как наши операции входа и выхода из очереди могут выполняться в начале или в хвосте очереди одновременно, то, строго говоря, это не обычная очередь, адека.
Наибольшая полезность монотонных очередей или монотонных стеков обусловлена тем, чтоЭлементы в контейнере увеличиваются или уменьшаются,такЭлемент на вершине стека или во главе очереди является наиболее ценным.. Используя монотонный стек, можно получить несколько максимумов на определенном интервале за постоянное время, в некоторых задачах толькоОдного получения наилучшего результата недостаточно. Из-за различных условий максимальное значение может быть не обязательно установлено.В это время необходимо найти второе максимальное значение или третье максимальное значение.В этом случае очень необходимо использовать монотонный стек или монотонную очередь . . .
как сегодняшняя дискуссияМультипакПроблема в том, что это так.
Фундаментальный анализ
Давайте сначала отложим в сторону монотонную очередь и внимательно проанализируем тему.
В предыдущих статьях мы обсуждали сложность алгоритмов динамического программирования. Для алгоритма динамического программирования нам нужно сделать следующее:пройти через все решения, и состояния, к которым может быть применено решение,Найдите лучший переход для каждого состояния, запишите эти лучшие результаты передачи. Лучшее значение среди всех результатов — это ответ на весь вопрос, который мы ищем. Тогда мы можем легко вывести сложность динамического программирования, которая равна количеству состояний, умноженному на количество решений.
Мы помним этот простой вывод, который может помочь нам легко анализировать сложность алгоритмов динамического программирования, особенно когда неудобно анализировать некоторые традиционные методы.
Мы делаем вывод о сложности задачи о множественных рюкзаках, для которой наше решение определяется двумя условиями. Один из них — это товар, а другой — количество этого товара. такКоличество решений равно количеству пунктов, умноженному на количество пунктов., состояние вместимость рюкзака. Предположим, что количество предметов равно N, количество предметов равно M, а вместимость рюкзака V, тогда его сложность равна
. Очевидно, что в подавляющем большинстве случаев такая сложность неприемлема, поэтому необходимо вводить различные оптимизации.
В предыдущей статье мы использовали двоичную запись, чтобы разделить количество элементов на сумму нескольких степеней двойки. Таким образом, для двоичной записи ее сложность равна
. Мы уменьшаем размерность M с помощью двоичного представления до
, то есть ли способ еще больше упростить его?
Конечно есть, продолжаем анализировать. Среди трех измерений NVM никоим образом нельзя уменьшить N. Независимо от того, какие у нас есть N видов предметов, мы должны сравнить плюсы и минусы этих N предметов.Невозможно сказать, что существуют стратегии для получения наилучших результатов без их рассмотрения.Это невозможно. Поскольку измерение N нельзя переместить, мы можем начать только с двух измерений VM.
Этот M довольно раздражает, можем ли мы придумать способ избавиться от него?
В наивной идее нам нужно пройти через количество выборок, чтобы найти оптимальную подструктуру. Например, если текущим состоянием является i, нам нужно обойти все j в 0-M, чтобы увидеть, какие j передачи получают оптимальное решение dp[i]. Так есть ли способ получить его автоматически без перечисления?
Конечно есть, и в этом тоже суть оптимизации монотонной очереди.
Монотонная очередь
Далее, давайте по крупицам выведем процесс монотонной оптимизации.
Сначала предположим, что текущее пройденное состояние равно i, то есть вместимость рюкзака равна i, текущий предмет — предмет, его объем — v, его стоимость — p, а его количество — n. Давайте начнем с первого понимания, для состояния i,Его можно получить только из перехода состояния i-kv. k здесь целое число в диапазоне [0, min(i/v, n)]. Я думаю, что каждый может понять формулу min(i/v, n), которая показывает, сколько текущего состояния я может содержать в самый пункт. Это количество является меньшим из верхнего предела n числа элементов и максимального количества i/v, которое может содержать не более чем состояние i. Мы называем значение min(i/v, n) cnt.
То есть для состояния i оно содержит не более cnt элементов и не менее 0. Тогда его возможности перехода равны только cnt, и переход из других состояний, таких как i-1 и i-2, невозможен. Мы пишем это уравнение перехода состояния, мы можем получить:
То есть по текущему пункту, то есть текущему решению, лучший результат состояния i должен быть получен путем передачи одного из ряда определенных подсостояний, и эти подсостояния связаны с целым числом k, и диапазон значений k равен [0, cnt]. Давайте пока проигнорируем эту область и упростим задачу. Рассмотрим самый крайний случай. В самом крайнем случае достаточно количества элементов. В этом случае мы можем перечислить все состояния, которые можно передать i через элемент. Это последовательность: [i % v, i % v + v, i % v + 2v, ..., i - v].
В предыдущем голом подходе мы проходим эту последовательность через цикл и находим из нее лучший переход. мыТеперь я надеюсь, что смогу сделать это, не пересекая, с помощью какого-либо метода быстро найти оптимальное состояние для перехода. Эту логику нетрудно понять, пока мы не вводили никаких замысловатых операций.
Давайте проведем простой анализ ниже, мы перечислили все возможные восходящие состояния для перехода в состояние i. Мы не хотим обходиться, чтобы найти лучший переход среди них Следуя этой идее, мы, вероятно, можем догадаться,Должен быть какой-то способ найти некоторое максимальное значение в этой последовательности. Только так мы можем быстро найти ответ без обхода. Но каким методом и что самое ценное мы пока не знаем. На данный момент мы сделали еще один шаг вперед и, вероятно, знаем следующую стратегию, но пока не знаем конкретных деталей, не беда, отложим это в сторону и продолжим анализ.
Чтобы упростить запись, мыПусть m = i % v, который является остатком от текущего состояния до объема элемента. Тогда вышеуказанная последовательность может быть записана как [m, m+v, m+2v, ... i - v]. Поскольку в этой задаче мы хотим, чтобы значение в рюкзаке было как можно больше, очевидно, что оно возрастает для последовательности dp[m], dp[m+v], dp[m+2v]... . Причина тоже очень проста: для каждого состояния в массиве dp хранится соответствующий ему оптимальный результат. Таким образом, мы не можем использовать больше места, но меньше ценности в рюкзаке.
Мы, конечно, надеемся, что сможем просто выбрать наибольшую из последовательности dp[m], dp[m+v], dp[m+2v]...dp[iv], но в силу сделанного выше вывода мы не можем Сделай это. Есть две причины, по которым это невозможно сделать, одна только что сказала, потому что dp[i] — этоПоследовательность, которая увеличивается по мере увеличения i, Чем больше вещей упаковано в кузове, тем больше стоимость посылки, и она не уменьшится. Другая причинапосле эффекта, эта проблема чем-то похожа на случай с рюкзаком ноль-единица. Например, например, dp[m] = x, если dp[m+v]=x+p, то есть dp[m+v] переносится из dp[m], а это значит, что он загрузил пункт пункт . Если мы перейдем от dp[m+v], мы не сможем судить, сколько всего предметов было взято, и мы не можем судить, является ли это незаконным.
Давайте решим эти две проблемы одну за другой, сначала поговорим о второй проблеме. Есть много способов решить эту проблему, самый простой из нихСохраните результат этой последовательности в отдельной копии, так что это не повлияет, когда мы обновим dp. В рюкзаке ноль-один мы решаем эту проблему траверсом в флешбэках, а вот в мультирюкзаке этот способ не подходит. Тогда давайте посмотрим на первую проблему. Причина, по которой невозможно напрямую найти максимальное значение последовательности, заключается в том, что неравенство, вызванное вместимостью рюкзака, Чтобы решить проблему, нам нужно найти способ устранить это неравенство. . Способ устранения тоже прост.Мы можем как-то поместить эти значения в один и тот же бенчмарк, чтобы устранить несправедливость, вызванную изменением емкости.
На самом деле этот бенчмарк найти несложно, т.е. Мы предполагаем, что значения в последовательности dp[m], dp[m+v], dp[m+2v]...dp[i-v] передаются через dp[m]. Например, dp[m+v], если оно получается переносом из dp[m], то dp[m+v] должно быть равно dp[m]+p. Точно так же dp[m+2v] должно быть равно dp[m]+2p. Обратите внимание,Данные здесь представляют собой результаты, которые не были обновлены по элементам элементов., значение, полученное после обновления последнего элемента. Таким образом, dp[m+v] здесь не должна получаться переносом dp[m], если dp[m+v] - p > dp[m], то, очевидно, можно показать, что потенциал dp[m +v] выше, чем у dp [m] больше, потому что создает большую ценность для того же объема v. Точно так же, если dp[m+2v] - 2p > dp[m+v] - p, то значение dp[m+2v] больше. И так далее, мы можем получить совершенно новую последовательность:
[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]
На этот раз мы устранили отклонение, вызванное изменением вместимости рюкзака, и можем смело выбирать из него наибольшее значение в качестве наилучшего перехода состояния. Но есть небольшая проблема,Возможно, что максимальное значение не установлено, например, если мы обнаружим, что значение dp[m+2v] - 2p является наибольшим, но так как элемент item получает не более cnt, то при переходе из состояния m+2v в i искомое число превышает cnt, тогда это тоже неверный перенос. Нам нужно оставить это позади и продолжить поиск неоптимальных результатов.
Для поддержания наибольшего значения в интервале очень подходит монотонная очередь.Мы можем гарантировать, что элемент во главе команды является оптимальным.Если элемент во главе команды недействителен, то мы можем легко вытолкнуть до получения субоптимального решения. Другими словами, мы сохраняем [dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[iv] - (i div v - 1)p] через монотонная очередь Максимальное значение этого интервала, который также является наиболее часто используемым сценарием для монотонных очередей.
Поток алгоритма
Давайте разберем вышеизложенные идеи, и мы сможем разобраться в процессе запуска всего алгоритма.
Сначала нам нужноЦикл для перебора элементов, это точно не пройдет. Независимо от того, какой алгоритм или оптимизация используется, нам нужно пройти через элемент, а элемент является основой решения. В рюкзаке 01 и двоичной записи второй цикл предназначен для прямого обхода емкости рюкзака. Но, очевидно, в текущем алгоритме мы не можем этого сделать. Поскольку, как упоминалось выше, нам нужно использовать монотонную очередь для обслуживания [dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[iv] - (i div v - 1)p] такая последовательность, поэтому нам нужно пройти емкость рюкзака в порядке этой последовательности. Заметим, что начальным состоянием является dp[m],Этот m представляет собой группировку, которая является остатком объема элемента.
Например, если объем товара i равен 5, то m имеет пять значений 0, 1, 2, 3 и 4, что на самом деле является остатком от 5. эквивалентно намВместимость группового рюкзака по остатку, так что мы поддерживаем последовательности в разных группах. Эти группы собраны вместе, чтобы сформировать всю вместимость рюкзака.
Давайте взглянем на приведенный ниже код, который будет более интуитивным в сочетании с приведенным выше описанием:
from collections import deque
items = [(10, 3, 5), (5, 6, 3), (2, 2, 4)]
if __name__ == '__main__':
volume = 20
dp = [0 for _ in range(volume+1)]
# 单调队列
deq = deque()
for item in items:
cnt, v, p = item
for i in range(v):
# 每个i代表一组新的序列
# 所以队列需要清空重新开始
deq.clear()
m = (volume - i) // v
for j in range(m+1):
val = dp[j * v + i] - j * p
while len(deq) > 0 and val >= deq[-1][0]:
deq.pop()
deq.append((val, j))
if deq[0][1] < j - cnt:
deq.popleft()
dp[j * v + i] = deq[0][0] + j * p
print(dp[20])
Так как мы хотим реализовать монотонную очередь, а операции чтения будут выполняться как с левого, так и с правого конца, мыРеализовано с использованием двусторонних очередей. В предыдущих статьях по темам Python мы представили использование deque в Python. Кроме того, в приведенном выше коде много деталей, давайте рассмотрим его по крупицам.
Во-первых, давайте посмотрим на переменную цикла.Самый внешний цикл — это элемент, который был определен.я петля остаток v. То есть остаток от веса предмета i, то есть общее количество предметов, сгруппированных по вместимости рюкзака для предмета i. Затем вычисляем оптимальное значение отдельно для каждой группировки. m представляет собой номер этой последовательности, то есть вместимость рюкзака за вычетом остатка, деленная на объем товара. Таким образом, последовательность, которую мы хотим сохранить, это [i, i+v, i+2v,..., i+mv], и j проходит через эту последовательность.
По честному,Мы используем dp[i] в качестве стандарта для измерения значения всей последовательности. Для состояния j * v + i мы вычитаем из него значение j элементов, то есть кладем его на начальную строку dp[i] для измерения значения. Итак, val = dp[j * v + i] - j * p.
Для монотонной очереди deqЭто убывающая очередь. То есть элемент в начале очереди является максимальным значением, а элемент в конце — минимальным значением. мыВставлять с конца каждый раз, извлекает все элементы меньше текущего, а затем мы вставляем текущее значение-кандидат. Согласно нашему предыдущему выводу, поскольку значения в массиве dp будут обновляться после одного раунда обхода, мыВам нужно хранить текущее значение и состояние вместе, а не только индекс, иначе при обновлении dp[j * v+ i] значение до обновления не будет найдено.
Эти граничные условия должны быть в порядке, проблема не очень большая, большая проблема заключается в оценке того, если deq[0][1]
Во-первых, у каждого узла в очереди deq есть два значения: одно — val, которое представляет собой значение, хранящееся в массиве dp, а другое — j, которое является позицией или состоянием последовательности.Обратите внимание, чтоОн не равен количеству взятых предметов. Из-за ограничения количества предметов в вопросе не все переводы являются законными. мыНеобходимо следить за тем, чтобы количество элементов, необходимых для перевода из состояния очереди в текущее состояние, было меньше или равно максимальному числу cnt, если больше недопустимо. Текущее состояние — j, а состояние элемента заголовка очереди — deq[0][1], что означает, что j - deq[0][1] > cnt недопустимо.
Поскольку значение элемента head в очереди deq самое большое, мы отдаем приоритет переходу из head в текущее состояние. Передача осуществляется путем взятия предметов, поэтому нам нужно судить о количестве предметов.Если он не соответствует потребностям, он будет выброшен.Это первый пункт.
Второй момент,Зачем использовать if для суждения вместо while??
Поскольку для j,Состояние j-1 было обновлено, что означает, что элемент в начале очереди должен быть допустимым для j-1.. То есть количество j-1 не больше cnt от j-1, поэтому для j оно увеличится не более чем на 1, и нам нужно всплывать не более одного раза. Конечно, вы также можете использовать цикл while, но это не обязательно. Так что, если вы этого не понимаете, это то же самое, что написать здесь цикл while.
Наконец, давайте проанализируем его сложность. Для предмета i, если его объем равен v, то всего мы можем разделить его на v групп. Количество в каждой группе равно объему / v, поэтомуПроизведение этих двух равно объему рюкзака V.количество штатов. Вы также можете подумать, что у нас есть накладные расходы на использование монотонной очереди, да, ноКаждый элемент входит и выходит из монотонной очереди не более одного раза, то есть для каждого набора последовательностей монотонная очередь
Сложность обхода такая же, как и сложность обхода, поэтому использование монотонной очереди не увеличит общую сложность шкалы, а только увеличит константу.
Суммировать
На этом этапе вводится монотонное оптимизационное решение для нескольких рюкзаков. Монотонная оптимизация — один из алгоритмов динамического программирования.Очень распространенный метод оптимизации, может быть применен не только к проблеме нескольких рюкзаков, но также применим во многих сценариях. Но предпосылка заключается в том, что нам нужно четко продумать отношения между состояниями и последствиями до и после передачи.
С точки зрения кода динамическое программирование действительно очень простое, как правило, не более нескольких десятков строк, а основная часть нашего алгоритма сегодня составляет всего 12 строк, но в этом коротком коде скрыто много информации и мыслей. . Для начинающих,Это нормально быть сбитым с толку, когда вы впервые узнаете, но успокойтесь хорошенько, поменьше обращайте внимания на некоторые термины, а больше думайте о некоторых существенных принципах.На самом деле это не так уж и сложно.Не понял один раз, прочитай несколько раз, и всегда будет момент, когда у вас есть вспышка вдохновения.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.