Девять лекций о рюкзаке

Задача о рюкзаке — одна из самых классических проблем в динамическом программировании.Можно сказать, что задача о рюкзаке полностью понята, что может очень помочь нам понять основной вывод уравнения переноса динамического программирования. Классическая лекция по проблеме рюкзака — «Девять лекций о ранце», написанная Цуй Тяньи из Чжэцзянского университета.Эта статья — мои заметки и впечатления в процессе прочтения статьи.

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

Основные концепции задач динамического программирования

Метод динамического программирования стремится найтиоптимальное основание«Определение состояний и уравнений перехода состояний после нахождения проблемы можно сформулировать как»Решить рекурсию, запомненную” метод решения.Найденное определение и есть суть динамического программирования.

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

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

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

Взяв в качестве примера простейшее число Фибоначчи, при решении 101-го члена нам нужно вычислить 100-й и 99-й члены, а при решении 102-го члена нам нужно решить 100-й и 101-й члены. Если бы мы использовали рекурсивный алгоритм напрямую, решение для элементов 101 и 102 привело бы к повторному вычислению элемента 100 дважды, что привело бы к потере большого количества времени.

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

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

Ключевые моменты алгоритма динамического программирования резюмируются следующим образом:

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

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

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

В то же время мы должны также отметить, что хотя динамическое программирование не имеет последствий, это не означает, что мы не можем использовать динамическое программирование для решения задач, требующих комбинации процессов, таких как: 140. Разбиение слов II.

0-1 Проблема с рюкзаком

тема

Есть N предметов и рюкзак вместимостью V. Стоимость размещения i-го предмета равна C1i, а итоговое значение равно Wi. Найдите, какие предметы положить в рюкзак, максимизируйте сумму значений.

Основная мысль

Самая основная проблема с рюкзаком, на предмет приходится только один предмет, и выбор только один: ставить или нет.

Мы можем определить матрицу состояний: F[i, v] представляет максимальное значение, которое можно получить, поместив первые i предметов в рюкзак вместимости v. Тогда его уравнение перехода состояния:

F[i,v]=maxF[i−1,v],F[i−1,v−Ci]+Wi

Просто проанализируйте приведенное выше уравнение: учитывая вместимость рюкзака v, необходимо рассмотреть подзадачу максимальной общей стоимости первых i предметов, только что помещенных в рюкзак.Положить ли i-й предмет в рюкзак. Когда текущий предмет не кладется в рюкзак, текущая общая стоимость равна общей стоимости первых i-1 предметов, только что положенных в рюкзак вместимостью v, а если он кладется в рюкзак, то первый i- 1 оставшийся предмет будет уменьшен на Small, текущая общая стоимость равна общей стоимости первых i -1 предметов, только что помещенных в рюкзак вместимостью v-Ci, плюс текущая стоимость предмета Wi. ** Мы преобразуем подзадачу «при заданной вместимости рюкзака v максимальная общая стоимость первых i предметов, которые помещаются в рюкзак» в подзадачу, которая касается только первых i-1 предметов. **В то же время мы используем двумерный массив для хранения матрицы состояний F[i, v] , что сокращает время повторных вычислений, вызванное перекрывающимися подзадачами.

оптимизация пространственной сложности

Пространственная сложность приведенной выше задачи равна O(VN), а временная сложность достигла оптимума, но есть место для оптимизации пространственной сложности.

Наблюдая за матрицей перехода состояний, мы обнаруживаем, что состояние i-го элемента часто зависит только от состояния i-1-го элемента, поэтому мы можем легко думать об использовании толькоМассив из двух строк хранит состояние в два момента, каждый раз, когда мы обновляем до i+1 элемента, мы позволяем состоянию i-го элемента перекрывать состояние i-1-го элемента, и в то же время позволяем состоянию текущего элемента заполнять вторую строку массив. Этот метод называетсяметод скользящего массива.

Но на самом деле мы можем дополнительно оптимизировать, чтобы использовать только одну строку массива для представления состояния. Наблюдая уравнение перехода состояния, мы обнаруживаем, что F[i, v] связано только с F[i-1, v] и F[i-1, vC], то есть с подсостоянием, от которого зависит текущее состояние , а количество столбцов должно быть меньше или равно текущему состоянию (v и vc). То есть: в"Заполнить форму ДП"когда,Текущая строка всегда ссылается на позицию «над головой» и позицию «вверху слева» строки над ней. Следовательно, мы можем открыть только одномерный массив и заполнить таблицу от начала до конца.

Причина, по которой нам нужно обновить состояние сзади вперед, заключается в том, что нам нужно использовать предыдущее состояние. При обновлении спереди назад исходное состояниеF[i-1,v] будет перезаписан новым состоянием F[i,v], что приводит к ошибке вычисления, которую невозможно найти, когда F[i-1,v] необходимо использовать позже.

С помощью сжатия состояний мы можем оптимизировать пространственную сложность до O(V) и решить задачу о рюкзаке 01, используя только один массив F[v].

• Пространственная сложность: O(VN)
• Временная сложность: O(V)

Начальные данные

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

Если требуется заполнить рюкзак ровно, то при инициализации кроме F[0] равно 0,Все остальные F[1..V] установлены в −∞, что гарантирует, что конечное F[V] является оптимальным решением, которое как раз заполняет рюкзак.

Если нет требования, чтобы рюкзак был полным, а только цена максимально большая,F[0..V ] должны быть установлены в 0 во время инициализации.Почему это? Это можно понять так: инициализированный массив F на самом деле является допустимым состоянием, когда в рюкзак нечего положить. Если требуется, чтобы рюкзак был точно полным, то только рюкзак с вместимостью 0 может быть «точно полным» ничем и значением 0, а рюкзаки с другими вместимостью не имеют законного решения и находятся в неопределенном состоянии, которое должно быть присвоено значение -∞. Если рюкзак не обязательно должен быть полным, то рюкзак любой вместимости имеет допустимое решение «ничего», значение этого решения равно 0, поэтому значение начального состояния равно 0.

пример

Пример задачи о рюкзаке 01: 416. Разделить подмножества с равной суммой.

Проблема в этой теме:Дан непустой массив, содержащий только положительные целые числа. Можно ли разбить этот массив на два подмножества так, чтобы суммы элементов двух подмножеств были равны.

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

Код для решения проблемы с рюкзаком 01:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        c=sum(nums)
        if c%2!=0:
            return False
        else:
            c//=2
        dp=[0 for _ in range(c+1)]#状态压缩
        for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算
            dp[j]=nums[0] if j>=nums[0] else 0
        for i in range(1,len(nums)):
            for j in range(len(dp)-1,nums[i]-1,-1):
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])#当前背包容量可以放入的最大价值物品（可以选取的最大整数和）
            if dp[-1]==c:#如果前i个物品恰好能填满容量为c的背包，即可选择一些整数，和为总元素和的一半
                return True
        return False

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

class Solution:
    def canPartition(self, nums: List[int]) -> bool:        
        c=sum(nums)
        if c%2!=0:
            return False
        else:
            c//=2
        dp=[0 for _ in range(c+1)]
        for j in range(len(dp)):#需要先初始化0号物品的情况，0号物品可以正向计算
            dp[j]=True if j==nums[0] else False
        for i in range(1,len(nums)):
            for j in range(len(dp)-1,nums[i]-1,-1):
                dp[j]=dp[j] or dp[j-nums[i]]#选或不选当前整数的两种情况下，只要有一种能填满当前背包容量即可将当前状态设为True
            if dp[-1]:#如果dp[c]为True，则说明可以选择一些整数，和为总元素和的一半
                return True
        return False

полная проблема с рюкзаком

тема

Есть N предметов и рюкзак вместимостью V. Стоимость размещения i-го предмета равна C1i, а итоговое значение равно Wi. Каждый предмет имеет неограниченное количество доступных. Найдите, какие предметы положить в рюкзак, максимизируйте сумму значений.

Основная мысль

Полная задача о рюкзаке, по-видимому, лишь немного отличается от задачи о рюкзаке 01, за исключением того, что полная задача о рюкзаке имеет произвольное количество вариантов для каждого элемента.

Мы можем легко придумать жадную идею:Отдавайте предпочтение экономичным товарам. Но есть еще проблема, то есть, хотя вы можете выбрать сколько угодно частей одного и того же предмета, он все равно может быть только в единицах штук, то есть один предмет нельзя разделить, вы не можете выбрать половина куска, вы можете выбрать только один кусок больше или выбрать один меньше. Это создает проблему.Часто невозможно заполнить весь рюкзак самыми экономичными предметами.Например,место в рюкзаке 10,а самый экономичный предмет занимает 7 места.Как заполнить оставшееся место?

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

Очень просто привести отрицательный пример, например, есть только два предмета: предмет A: стоимость 5, объем 5, предмет B: стоимость 8: объем 7, вместимость рюкзака 10, эффективность затрат на предмет B, очевидно, выше, чем у элемента A, то используйте жадность. Алгоритм неизбежно решит поместить один элемент B. В это время оставшееся место больше не может вместить A или B, поэтому наибольшее полученное значение равно 8. На самом деле, если вы выберите поставить два элемента A, вы можете получить более высокое значение. 10.Так что жадный алгоритм здесь не работает.

Мы рассматриваем с точки зрения каждого пункта связанную с ним стратегию, это не два вида взятия или нет,Вместо этого есть 0 штук, 1 часть, 2 части... до тех пор, пока [V /Ci] штук не будет взято, и многие другие. Основываясь на задаче о рюкзаке 01, мы можем вывести ее формулу переноса динамического программирования как:

не трудно увидеть,Задача о рюкзаке 01 является частным случаем полной задачи о рюкзаке.Поскольку в это время необходимо пройти стратегии от 0 до [V /Ci], требуются три уровня перечисления, а общая временная сложность составляет

Простая и эффективная оптимизация: если два элемента i, j удовлетворяют Ci ≤ Cj и Wi ≥ Wj,Тогда элемент j можно удалить сразу без рассмотрения. В любом случае, маленькое и дорогое j можно заменить недорогим i, и полученное решение будет как минимум не хуже. Это не то же самое, что жадный алгоритм, потому что он не только должен быть рентабельным, но и вес предмета также должен быть меньше.

Преобразовано в 01 Задача о рюкзаке

Фактически, мы можем преобразовать полную задачу о рюкзаке в задачу о рюкзаке 01 следующим образом:Разделите различные варианты выбора предмета на несколько предметов в рюкзаке 01, где можно выбрать только 0 или 1.

Учитывая, что i-й элемент можно выбрать не более чем [V /Ci],Затем i-й предмет может быть преобразован в [V /Ci] предметов с постоянной стоимостью и ценностью.

Дальнейшая оптимизация, мы знаем, что, учитывая природу двоичных чисел, любое число может быть представлено как комбинация нескольких 2k. Итак, нам просто нужно разбить элементы на элементы log[V /Ci].

оптимизация пространственной сложности

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

Мы также можем использовать аналогичный метод, чтобы уменьшить пространственную сложность до O (N).Единственная разница между ним и задачей о рюкзаке 01 заключается в следующем:Нет необходимости перемещаться по таблице заполнения DP в обратном направлении, достаточно заполнения в прямом направлении.

Это связано с тем, что в задаче о рюкзаке 01 мы можем добавить не более 1 элемента одного типа, поэтому мы можем добавить только результаты первых i-1 элементов, а обход в обратном порядке должен предотвратить перезапись этого результата. . В полной задаче о рюкзаке мы можем добавить не более бесконечного числа предметов, мы можем продолжать добавлять результаты первых i предметов, и чтобы использовать результаты размещения первых i предметов, мы должны пройти вперед.

пример

Пример задачи с полным рюкзаком: Вопрос интервью 08.11 Монеты

Цель этой задачи состоит в том, чтобы: Учитывая неограниченное количество монет номиналом 25 центов, 10 центов, 5 центов и 1 цент, написать код для вычисления n центов несколькими способами. Очевидно, это полная задача о рюкзаке с рюкзаком вместимости n и четырьмя предметами, которые можно рассматривать как одинаковые по стоимости и весу. Здесь мы запрашиваем не максимальное значение, а количество комбинаций, которые просто заполняют рюкзак.

class Solution:
    def waysToChange(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        coins = [1, 5, 10, 25]
        for coin in coins:
            for i in range(1, n+1):
                dp[i] += dp[i-coin] if i-coin>=0 else 0
        return dp[-1] % 1000000007

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