Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня среда по алгоритмам и структурам данныхГлава 12Статья «Проблема рюкзака с нулевой единицей в динамическом программировании».
В предыдущих статьях мы вместе обсуждали бинарный, жадный алгоритмы, алгоритмы сортировки и поиска, сегодня мы рассмотрим еще один очень классический алгоритм —динамическое программирование.
В области соревнований acm-icpc динамическое программирование представляет собой очень большую категорию, которая содержит множество вариантов, и многие варианты чрезвычайно сложны. Например, выполнение динамического программирования на различных деревьях, графах и других структурах данных может очень усложнить задачу. К счастью, несоревновательным игрокам не нужно разбираться в этом так глубоко, вообще говоря, если вы досконально понимаете девять лекций по бэкпэкингу, этого достаточно, чтобы гордиться всевозможными интервью. Итак, мы начинаем целую новую главу по теме «Алгоритмы в среду» —Серия рюкзаков, Сегодня я поделюсь с вами первой лекцией из девяти лекций о рюкзаках, которая также является простейшей задачей о рюкзаке с нулевой единицей.
Рюкзаки и рюкзаки Zero One
Студенты без опыта соревнований могут быть сбиты с толку, когда увидят это название, какая связь между динамическим программированием и рюкзаками. На самом деле это не имеет значения, я не фанат Исона Чана, но в качестве названия рюкзака использовалась самая классическая задача динамического программирования того времени, и это также привело к различным вариантам. Позднее для удобства преподавания использовалось имя предшественника.
Мы упоминали о проблеме рюкзака в вопросе о воре Кидде, крадущем драгоценности, на самом деле это очень просто, то есть у нас есть рюкзак вместимостью V и n объемов v[i] соответственно, и значение равно w[i] из пяти продуктов. Извините, исходя из того, что позволяет вместимость рюкзака, мыПредметы максимальной ценности, которые можно получить?
Так как существует только один предмет каждого вида, то есть предмет имеет только два состояния взятия и не взятия, то эта задача называетсяЗадача о рюкзаке с ноль-единицей.
Жадность и контрпримеры
Первое, о чем мы думаем, — это жадный метод, например, отдавать приоритет товарам с высокой ценностью или товарам с высокой эффективностью затрат, но мы легко можем привести контрпримеры.
Например, если вместимость рюкзака 10, у нас есть 3 предмета, объем 6, 5, 5 и стоимость 10, 8, 8. Этот контрпример может доказать, что две жадные стратегии не работают, потому что наибольшее значение равно 10, а его объем равен 6. Как только мы его возьмем, нет места для дальнейшего получения других предметов, и, очевидно, случай взятия две пятерки лучше всего. Точно так же предметы с объемом 6 также являются наиболее рентабельными, и жадная стратегия приоритета рентабельности также не работает.
На самом деле, эти две жадные стратегии не только неэффективны,Все мыслимые жадные стратегии не работают. Эта проблема кажется простой, но решить ее не так-то просто. На самом деле эта проблема мучила ученых-компьютерщиков до 1960-х годов, когда появились алгоритмы динамического программирования, которые прекрасно решили эту проблему.
динамическое программирование
Английский алгоритм динамического программированияdynamic programming, очень простой перевод. Мы все очень хорошо понимаем планирование, но как понимать динамику? Как планировать динамически? Размышление над этой проблемой напрямую связано с природой алгоритма.
Суть алгоритма динамического программирования заключается в записи и переходе состояния.Вы когда-нибудь думали об этом в сочетании с вопросом только сейчас?Почему жадные алгоритмы невозможны? На самом деле это очень просто, потому что мы не можем быть уверены, в каком состоянии находится рюкзак. Хотя мы знаем, что вместимость рюкзака равна V, мы не знаем, сколько мы можем удержать в оптимальной ситуации и каково оптимальное конечное состояние. Мы считаем пространство V состоянием жадным, и результат, полученный жадностью, оптимален, но он только жаденОптимальное решение состояния, которое может быть достигнуто, не является глобальным оптимальным решением, из-за ограничения вместимости рюкзака очень вероятно, что мы не сможем достичь действительно оптимального состояния при жадной стратегии.
Чтобы пояснить приведенный выше абзац на примере, только что, по жадному алгоритму, мы выберем предмет с вместимостью 6 и значением 10. После того, как этот предмет взят, состояние рюкзака равно 6, а полученное значение это 10. Это состояние является конечным состоянием, которого может достичь жадность.Для этого состояния это оптимальное решение, но это состояние не является оптимальной ситуацией в целом, потому что при жадной стратегии невозможно достичь состояния, когда емкость 10 полностью заполнена. использованный.
Поняв проблему, естественно найти решение. Жадная стратегия может получить некоторые оптимальные состояния, тогда мыМожете ли вы записать оптимальную ситуацию, которой могут достичь все состояния?, и, наконец, выбрать оптимальную из этих оптимальных ситуаций, разве это не оптимальное решение в целом?
Динамическое программирование основано на вышеуказанных идеях и решает не оптимальное решение одного состояния, а оптимальное решение всех состояний.
состояние и переход
К этому моменту вы еще не должны понимать алгоритм динамического программирования, но у вас уже должно быть какое-то общее представление. Верно, наличие правильного чувства является предпосылкой правильного понимания. Давайте пойдем шаг за шагом и снова рассмотрим концепцию состояния.
Мы упоминали так много раз только что, каков статус? Это относительно абстрактное понятие, и в разных задачах оно имеет разное значение. В задаче о рюкзаке состояние относится кИспользование вместимости рюкзака. Так как объем предмета в задаче о ранце целое число, то очевидно, что возможность вместимости ранца ограничена, что незаметно, но очень важно.Если состояние не целое, то хотя и существует возможность динамического программирование, реализация кода может быть проблематичной.
Поняв, что вместимость рюкзака — это состояние, мы можем далее понять, что вместимость рюкзака будет меняться. Причина изменения в том, что мы кладем в него вещи, и после того, как вещи будут сложены, состояние рюкзака изменится,переходить из одного состояния в другое. В середине перехода состояния мы помещаем вещи. Объекты, которые мы помещаем, не являются фиксированными, но есть много вариантов. Мы решаем поставить A вместо BC. Это решение.Решения приводят к переходу состояний, разные решения приведут к разным переходам.
Например, сейчас есть рюкзак вместимостью 10, а мы поместили в него предмет объемом 3 и стоимостью 7. Если в это время мы решим добавить элемент с объемом 4 и значением 5. Тогда очевидно, что емкость, занимаемая рюкзаком, станет равной 7, а значение — 12. Этот процесс является классическим процессом перехода между состояниями, который также является ядром всего алгоритма динамического программирования.
Были введены основные понятия и идеи, и следующим шагом является использование этих понятий для решения практических задач.
оптимальное состояние
Как мы уже говорили ранее, динамическое программирование, в конце концов, получит оптимальное решение для всех состояний, а затем выберет глобальное оптимальное решение. Так как же получить локальное оптимальное решение?
Прежде чем ответить на этот вопрос, давайте рассмотрим два вопроса.
Прежде всего, если мы уже знаем, что максимальное значение рюкзака при объеме 3 равно 5, то решаем положить предмет объемом 4 и значением 5, тогда объем рюкзака увеличится до 7, то что мы получаем на данный момент, является оптимальным решением для тома 6?
На этот вопрос нетрудно ответить, после небольшого размышления мы знаем, что, скорее всего, нет. Для простейшего примера предположим, что у нас есть предмет с объемом 7 и стоимостью 20. Тогда это явно лучше, чем ставить эти два пункта. Хотя состояние 3 может получить самое большее значение 5, а состояние 7 также может быть переведено из состояния 3, это не обязательно оптимально.То есть, когда передается оптимальное состояние, не обязательно возможно получить оптимальное значение других состояний..
Если мы реверсируем задачу, если мы знаем оптимальное решение для тома 6, а также знаем, что оно получается переносом объема, равного 4, можем ли мы быть уверены, что состояние тома 4 также является соответствующим оптимальным решением?
На этот раз ответ изменился, и это правильно, потому что если есть лучшее решение для тома 4, то и том 6 должен быть лучше, что противоречит нашему предположению.
Резюмируем два предыдущих вывода, т.Перенос локальной оптимальной ситуации не обязательно оптимален, но локальный оптимум также должен быть получен переносом других локальных оптимальных состояний.. Это предложение немного похоже на скороговорку, но я не думаю, что это должно быть сложно объяснить. Это как студент, который идет на экзамен, может быть, ты и не сможешь занять первое место, но тот, кто получит первое, должен быть студентом. Локальный оптимум — лучший ученик, а перевод — экзамен. Локальный оптимальный перенос не обязательно является оптимальным состоянием после переноса.Могут быть и другие лучшие стратегии переноса, но для того, чтобы определенное состояние было оптимальным, оно также должно быть из предыдущего оптимального состояния.
И переход состояния такжеПоследовательный, например, в этом вопросе объем предметов, помещаемых в рюкзак, может только увеличиваться, но не может уменьшаться, а значит, состояние может быть переведено только от малого к большому.
Поразмыслив, мы выяснили, что состояния могут быть перенесены, и перенос состояний имеет порядок, и локальный оптимум должен быть получен путем переноса других локальных оптимумов. Поскольку мы не знаем, может ли текущий переход достичь оптимального состояния, мыВам нужно использовать массив или контейнер для записи максимального значения, которого когда-либо достигали все состояния в истории.. Наконец, из всех максимальных значений выбирается еще одно, что и является решением итоговой задачи.
На данный момент, если это общая проблема динамического программирования, она решена, но есть еще одна деталь, которую следует рассмотреть для рюкзака ноль-единица.
нет последействия
Давайте посмотрим на весь процесс расчета.Во-первых, нам нужно начать с начального состояния.Это начальное состояние легко обработать, то есть, когда рюкзак пуст, значение в это время равно 0, а объем также 0, что также является его оптимальным состоянием, это легко понять, ведь мы не можем создать что-то из ничего.
Итак, мы начинаем с 0 для передачи состояния, и передача состояния сопровождается решением, которое отражается в выборе различных пунктов в этой задаче. Мы проходим элементы как решения, затем проходим состояния, к которым эти решения могут быть применены, и получаем все переходы между состояниями. Наконец, мы используем контейнер для записи локальных оптимальных решений, достигнутых во время всех переходов состояний, и все.
Этот процесс выглядит вполне нормально без каких-либо исключений, но на самом деле проблема грядет.
Также используем в качестве примера предыдущую тему Вместимость рюкзака 10, 3 предмета, объем 6, 5, 5, стоимость 10, 8, 9. Мы берем третий элемент, начиная с 0, и переходим в состояние 5, где значение равно 9. В это время, если мы продолжим движение назад, мы перейдем к состоянию 5, которое уже приняло элемент 3 и информацию стоимостью 9. Поскольку предмет можно взять только один раз, мыБольше нельзя использовать пункт 3 для передачи состояния 5, иначе это нарушает смысл вопроса.
Вы можете сказать, что эта задача несложная, мы также можем записывать предыдущие решения в состояние, если мы добавляем суждение при принятии решения.
На столе кажется, что это из-за ограничения, что предмет нельзя брать повторно, но на самом деле это из-за влияния между нашими состояниями. Другими словами, решения, которые мы принимаем на переднем плане, вероятно, повлияют на принятие решений в следующих состояниях. Эффекты до и после между этими состояниями называютсяпосле эффекта. Очевидно, что мы не можем использовать алгоритм динамического программирования в сценариях с последействием.Не все проблемы можно решить добавлением суждений.Нам необходимо решить существенную проблему последействий, то есть мы должны найти способ устранения последействий.пол .
В данной задаче это легко сделать. Нам нужно только контролировать порядок обхода состояний и решений,Отделяйте предыдущие решения от более поздних решений, чтобы они не влияли друг на друга. Если мы сначала пройдемся по состояниям, а затем пройдемся по действиям, которые можно предпринять в каждом состоянии, неизбежно будет прямое воздействие. Потому что решения, принятые в прошлом, не могут быть приняты позже. Но тыл не может воспринять, какое решение было принято спереди. Таким образом, лучший подход состоит в том, чтобы сначала пройти через решение, а затем пройти через состояния, в которых решение может быть принято. Во избежание взаимного влияния до и после принятия решения мы принимаемСостояния обхода в обратном порядке.
Давайте возьмем пример, предположив, что вместимость рюкзака по-прежнему равна 10, первый элемент, который мы перечисляем, имеет объем 3 и значение 5. Мы пересекаем состояния с 7 по 0 в воспоминаниях, потому что для состояний больше 7 это решение не может быть принято (общий объем превысит). Поскольку для состояний больше 7 мы не можем принять это решение (общий объем превысит лимит), для состояния 7 мы можем принять это решение и перейти в состояние 10. Мы не знаем, будет ли этот перенос оптимальным, поэтому записываем его так: dp[10] = max(dp[10], dp[3] + 5).
Затем мы пересекаем том 6 и можем перейти в состояние 9.
Поскольку мы перемещаемся в обратном порядке, когда мы обновляем состояние 10 состоянием 7, само состояние 7 не обновляется этим решением. Даже если мы обновим состояние 7 позже, когда перейдем к состоянию 4, это не повлияет на результат состояния 10. Поскольку он проходится в обратном порядке,Мы не будем снова обновляться до состояния 10 с той же стратегией.. Если это обход положительного порядка, его нельзя избежать. Для одного и того же элемента очень вероятно, что мы будем использовать состояние 1 для обновления состояния 4, затем использовать состояние 4 для обновления состояния 7, а затем использовать состояние 7 для обновления состояния 10. Эта ситуация фактически соответствует использованию нескольких одинаковых предметов, что противоречит смыслу названия.
Например, предположим, что есть предмет с объемом 2 и стоимостью 5. Когда мы проходим состояние 0, мы обновляем состояние 2, мы переходим в состояние 2, обновляем состояние 4 тем же элементом и получаем 10. Тогда для состояния 4 это фактически эквивалентно взятию 2 из этого элемента, то есть оно дважды обновляется одним и тем же решением. Но у нас есть максимум один элемент, что явно неправильно.
В динамическом программировании, из-за невозможности определить источник текущего перечисляемого состояния, не допускается его появление после эффектов.Если его нельзя решить, динамическое программирование использовать нельзя. Это также самый основной принцип динамического программирования.В этой задаче мы ловко трансформировали процесс принятия решений и перечисления состояний, чтобы устранить последствия. В других темах может быть не так, и надо судить по реальной ситуации.
Если вы забываете о предпосылке динамического программирования в процессе обдумывания проблемы, подумайте о ситуации с подбором предметов в рюкзаке ноль-один. Есть только один предмет, и взять его можно только один раз. Если вы берете его перед собой и можете взять позже, это нарушает последействие.
уравнение перехода состояния
Давайте сейчас разберемся с идеями о переходе между состояниями.Есть следующие моменты:
- Начнем с состояния 0, где оптимальное значение равно 0.
- Рассмотрите вопрос о последствиях, чтобы гарантировать отсутствие последствий.
- При выполнении решения происходит переход состояния и записывается оптимальное решение, соответствующее состоянию.
В этом вопросеРешение — приобрести предмет, а состояние — вместимость рюкзака.. Поскольку взятие предметов приведет к изменению вместимости рюкзака, а на каждый предмет приходится только один предмет, во избежание последствий нам нужно сначала перечислить решения, а затем перечислить состояния, чтобы убедиться, что каждое решение является только применяется к каждому состоянию не более одного раза. В ходе этого процесса необходимо постоянно фиксировать оптимальное решение для каждого состояния.
Поскольку вместимость рюкзака равна V, нам нужно использовать только массив вместимости V для записи всех состояний.
dp[0 for _ in range(V)]
for i in items:
for v from V-i.v to 0:
dp[v + v[i]] = max(dp[v+i.v], dp[v] + i.w)
return max(dp)
dp записывает все состояния, мы используем max(dp[v+iv], dp[v] + iw) для обновления значения состояния dp[v+iv], так как текущее решение не обязательно лучше предыдущего , Поэтому добавьте операцию max, чтобы гарантировать, что результат, записываемый каждым состоянием, является оптимальным. Когда доступны оптимальные решения для всех состояний, очевидно, что оптимальное решение всей задачи также находится в нем.
Приведенная выше формула для записи процесса перехода состояния называетсяуравнение перехода состояния, что также является основной концепцией алгоритмов динамического программирования. Много раз, когда мы решаем задачи динамического программирования, мы выводим уравнения перехода состояний на бумаге. Если можно четко перечислить уравнения перехода состояний, это недалеко от написания кода.
код
Приведенное выше уравнение переноса очень близко к окончательному коду, и на самом деле написано всего несколько строк:
dp = [0 for _ in range(11)]
items = [[6, 10], [5, 8], [5, 9]]
# 遍历物品
for v, w in items:
# 遍历背包空间（状态）
# 由于要放入物品，所以从空间10-v开始遍历到0
# 更新vp+v的状态，即当前容量放入物品之后的状态
for vp in range(10-v, -1, -1):
dp[vp+v] = max(dp[vp+v], dp[vp] + w)
print(max(dp]))
Суммировать
Вывод до и после рюкзака ноль-единица и все концепции в нем даже представлены.Хотя мы использовали так много места, чтобы представить этот алгоритм, фактический код составляет всего несколько строк. С точки зрения количества строк кода, динамическое программирование можно назвать алгоритмом с кратчайшим кодом, но хотя его код не длинный, идея не проста, особенно детали нижнего индекса и порядка. петли, я надеюсь, вы не относитесь к этому легкомысленно.
На сегодня проблема с рюкзаком ноль-единица закончена, на следующей неделе мы продолжим тему с рюкзаком и рассмотрим расширенную версию рюкзака 01-Полные рюкзаки и мультипакивопросы, следите за новостями.
Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.