Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняВыпуск 13 специальных тем в алгоритмических структурах данныхСтатья также является второй по теме динамического программирования.
В предыдущей лекции мы вместе изучили задачу о рюкзаке ноль-единица в алгоритме динамического программирования.Мы знаем, что так называемый рюкзак ноль-единица означает, что каждый предмет имеет только один, поэтому его состояние только 0 и 1, то есть , брать или не брать. Сегодня мы обсудим ситуацию, когда есть более одного элемента.Есть более одного элемента и есть два типа.Во-первых, нет никаких ограничений, и их столько, сколько вы хотите.Это называется Полная задача о рюкзаке Другая проблема заключается в том, что количество предметов все еще ограничено, это называется проблемой нескольких рюкзаков.
Давайте рассмотрим их один за другим, начиная с более простого комплектного рюкзака. Поскольку это непрерывная тема, студенты, которые не читали предыдущую статью или новичок, могут перейти к первой статье нашей темы:
полный рюкзак
В предыдущих статьях мы объясняли, как динамическое программированиеСостояние и решение и переход состоянияродственные понятия. В задаче о рюкзаке вместимость рюкзака — это состояние, а какой предмет выбрать для приобретения — это решение Когда мы примем решение, рюкзак перейдет из одного состояния в другое. Алгоритм динамического программирования заключается в перечислении всех состояний и решений, получении всех переходов между состояниями иЗапишите оптимальное решение, которое может быть получено для каждого состояния в этом процессе..
В предыдущей статье мы сначала прошлись по всем решениям, затем перебрали все состояния и вычислили результат перехода по решению. В предыдущей задаче о рюкзаке ноль-один, поскольку мы можем получить только один предмет за предмет, если решение принято в предыдущем состоянии, последнее состояние не может принять такое же решение. это динамическое программированиепосле эффекта, а в полной задаче о рюкзаке мы снимаем это ограничение, что означает, что больше нет никакого последующего эффекта между решениями, и решение может быть повторно применено к каждому состоянию.
Итак, если вы можете понять приведенный выше абзац, то весь алгоритм на самом деле очень прост, почти как код рюкзака ноль-единица. Просто мы «исправляем» состояние рюкзака при обходе воспоминаний.
Раньше, во избежание повторного приобретения предметов, мы приняли метод обхода воспоминаний, а теперь мы больше не ограничиваем количество, а значит, можем свободно принимать решения о передаче. Для этого используется простой двойной цикл: первый — перечисление решений, второй — перечисление состояний и запись оптимальных решений, которые могут принести все переходы. Давайте посмотрим на код:
dp = [0 for _ in range(11)]
items = [[6, 10], [5, 8], [5, 9]]
# 遍历物品
for v, w in items:
# 遍历背包空间（状态）
# 更新vp+v的状态，即当前容量放入物品之后的状态
for vp in range(0, 10-v+1):
dp[vp+v] = max(dp[vp+v], dp[vp] + w)
print(max(dp]))
Если вы не до конца поняли логику, мы можем посмотреть код, чтобы понять его. В первом цикле мы перебираем все элементы, каждый элемент соответствует решению. Каждое решение может быть применено к каждому состоянию, например, первый элемент равен 6, 15, что означает, что его объем равен 6, а его значение равно 15. Затем мы проходим все состояния, где это решение может быть применено, т. е. вНе превышайте вместимость рюкзакаСостояние, которое может быть подавлено при данных обстоятельствах. Очевидно, что для элемента объемом 6 можно проставить только состояния от 0 до 4. Например, если мы выберем состояние 2, то после того, как элемент будет помещен в состояние 2, он естественным образом перейдет в состояние 8, потому что объем увеличился на 6. Возможно, это решение приведет к лучшему результату для состояния 8, а может и нет, если мы обновим значение записи состояния 8. Этот процесс принятия решения из одного состояния в другое является переходом состояния.
Полный рюкзак этоНеограниченное издание рюкзака Zero One, в принципе, идеи и практики этих двух в основном одинаковы. Если вы понимаете, что такое рюкзак ноль-единица, то полный рюкзак не должен быть для вас проблемой.
небольшая оптимизация
В комплекте рюкзак, так как все предметы можно добывать бесконечно. Таким образом, мы можем ввести некоторые оптимизации, которые не может выполнить рюкзак с нулевой единицей, напримерДля предметов одного объема мы можем оставить только предмет с наибольшей ценностью., чтобы отфильтровать другие элементы. Эта идея очень проста, я думаю, каждый должен быть в состоянии понять.
Например, два элемента имеют объем 3, один имеет значение 4, а другой имеет значение 3. Мы можем полностью игнорировать элемент со значением 3. Потому что государственная передача, принесенная двумя, одинакова, но первая явно лучше. И эта оптимизация невозможна в рюкзаке с нулевой единицей, потому что у каждого предмета есть только одна,Очень вероятно, что произойдет и то, и другое, поэтому его нельзя просто заменить. В комплектном ранце такой проблемы нет.
Мультипак
По сравнению с рюкзаком ноль-один и комплектным рюкзаком мультипак сложнее, и его решения тоже весьма разнообразны. Давайте посмотрим на некоторые относительно простые методы сегодня.
Опять же, начнем с самого простого способа. Самый простой способ, конечноПреобразование нескольких рюкзаков в рюкзаки с нулевым единицейДля решения задачи, например, предмет можно взять не более N, мы разделим его на N видов предметов, и каждый из этих N видов предметов может взять не более одного, что эквивалентно тому, что мы можем взять до N одного ст. Эта идея должна быть очень простой, и ее может понять каждый, но есть большая проблема — сложность. Конечно, мы можем провести некоторую оптимизацию по объему рюкзака, например, когда количество предметов превышает вместимость рюкзака, мы можем убрать лишнюю вместимость, ноОбщая сложность по-прежнему очень высока. Особенно когда у нас большой рюкзак.
Итак, как нам решить эту проблему?
Вот более общий алгоритм, который можно использовать для оптимизации многих задач, а также идея многих алгоритмов. этодвоичная запись. Мы упоминали этот метод в предыдущей статье, идея очень проста, но очень практична.
двоичная запись
Так называемое двоичное представление состоит в том, чтобы представить число типа int в двоичном виде.Идея всего алгоритма заключается в этом предложении, поэтому я думаю, что каждый должен быть в состоянии понять его. Но почему мы конвертируем int в двоичный и как оптимизировать алгоритм после преобразования в двоичный, это то, что мы хотим знать, и это основная цель алгоритма, не волнуйтесь, давайте немного объясним .
Все мы знаем, что все данные в компьютерных системах хранятся в двоичном формате, наиболее типичными из которых являются целые числа. 32-битное целое число, которое может представлять целые числа до 2,1 миллиарда. Это все нам известно, но с другой точки зрения, число 2,1 миллиарда, наконец, представлено 32 двоичными битами, что на самом деле довольно удивительно. Почему двоичный код — отличная идея? Не потому, что это сложно, а потому, что эффективно сжимает данные.
Давайте посмотрим подробнее, почему 32 двоичных бита могут представлять такой большой объем данных? Поскольку данные, представленные этими 32-битными целыми числами, различны, 0-й бит представляет 1, 1-й бит представляет 2, второй бит представляет 4... Когда он достигает 31-го бита, представленное число уже очень велико. Мы используем различные комбинации этих 32 чисел для представления разных чисел, другими словами, все числа в диапазоне в конечном итоге становятся суммой нескольких из этих 32 чисел. Запишем формулу так:,здесьУказывает коэффициент i-го бита, который имеет только два значения 0 и 1.
Эта формула знакома всем, но многим она может быть непонятна, когда мы применяем ее к уравнению. Например, если функция удовлетворяет следующим свойствам:, если вы прямо проситеЭто очень хлопотно или дорого, мы можем использоватьичтобы получить. Точно так же, когда мы используем его в двоичном формате, мы можем получить:
Смотрите, мы ставимВ некоторых сценариях значение преобразуется в сумму до 32 значений.легко вычислить, ноЭто трудно вычислить напрямую, в это время нам будет очень просто преобразовать в двоичный код.
Точно так же, если накопление понято, накопление придет естественным образом. если функцияудовлетворить:, то мы также можем использовать двоичный код для выражения:
Для задачи о нескольких рюкзаках, очевидно, мыУдовлетворение – это накопительное свойство. То есть для большего x мы можем накапливать его с несколькими подсостояниями. так как, так что мы можем легко найти,, то есть существует множественная связь между этими подсостояниями. Следовательно, мы можем легко вычислить эти подсостояния, а затем аккумулировать их в соответствии с двоичным представлением x, чтобы получить, при непосредственном вычисленииЭто намного сложнее и требует больших вычислительных ресурсов.
В этой задаче функция f представляет значение элемента, который мы берем. Другими словами, если существует не более n элементов определенного предмета, а стоимость одного предмета равна p, то мы принимаем 2 за 2p, а 4 за 4p. степени 2. вычислить. Нам нужно перечислить ситуации, когда берутся эти n элементов, и диапазон нашего перечисления должен быть [0, n]. После преобразования n в двоичное число мы можем получить любое число из [0, n], суммируя комбинацию logn степеней двойки. тогда мыПросто относитесь к предметам со степенью двойки как к новым предметам., так что мы можем использовать комбинацию 01 нового элемента для замены всех случаев, когда исходный элемент принимает 0-n.
Например, у нас всего 15 элементов, значение равно 3, где 15=, то есть мы можем использовать 4 двоичных бита для представления числа 1-15. Затем, после того как мы сопоставим эти 4 двоичных бита с 4 элементами, мы можем использовать комбинацию этих 4 элементов для представления приобретения 1-15 исходных элементов. То есть мы поместили 15 предметов ценности 3 в четыре пачки: одну в первую пачку, две во вторую пачку, четыре в третью пачку и четыре в четвертую восьмерку. Если мы хотим взять 3 оригинальных предмета, это равносильно тому, чтобы взять первый и второй пакеты. Если мы хотим взять 5 оригинальных предметов, это равносильно тому, чтобы взять первый и третий пакеты.Таким образом, мы преобразуем проблему нескольких рюкзаков обратно к задаче о рюкзаке с нулевой единицей..
Как мы уже говорили, 32 двоичных бита могут представлять более 2 миллиардов чисел, поэтому, хотя количество элементов увеличится после того, как мы выполним двоичную обработку, оно также очень ограничено. Проведем простой анализ сложности, предположив, что общее количество предметов равно N, количество каждого предмета не превышает M, а вместимость рюкзака равна V. Если используется наивный метод разделения, сложность, в то время как сложность использования бинарного разделения составляет. По сравнению с предыдущим переход от M к logM — это огромная оптимизация, особенно когда M велико.
Наконец, есть небольшая проблема,Наше количество предметов не обязательно делится на сумму числа степеней двойки., что мне делать в этом случае? На самом деле это тоже просто, мы просто делаем отдельный пакет для остальных частей. Например, если предметов 10, 10=1+2+4+3, значит, последний мешок — 3. Хотя мы также можем представить 3 с помощью 1+2, это не влияет на правильность результата.
На данный момент было введено решение нескольких рюкзаков, и так много было сказано, что это всего лишь метод двоичного представления. Поняв этот метод, он трансформируется в рюкзак ноль-единица. Я должен сказать, что этот метод действительно гениален и имеет аналогичные приложения во многих других задачах, помимо задачи о рюкзаке. Так что этот метод не рекомендуется пропускать.
Наконец, давайте посмотрим на код.Сначала давайте посмотрим на часть двоичного разделения:
def binary_divide(cnt, volume, price):
divides = []
for i in range(32):
# 从0位开始枚举
cur = 1 << i
# 如果小于枚举值，说明已经拆分完毕了
if cnt < cur:
# 把剩下的部分打包
divides.append((cnt, cnt * volume, cnt * price))
break
else:
# 否则继续拆分，打包1 << i个物品
cnt -= cur
divides.append((cur, cur * volume, cur * price))
return divides
После бинарного разделения задача превращается в рюкзак с нулем и единицей. Нам просто нужно применить код рюкзака ноль-единица:
# 物品，分别是数量，体积和单位价格
items = [(10, 3, 5), (5, 6, 3), (2, 2, 4)]
volume = 20
dp = [0 for _ in range(volume+1)]
new_items = []
for i in items:
# 二进制拆分
new_items.extend(binary_divide(*i))
for item in new_items:
v, p = item[1], item[2]
for i in range(volume-v, -1, -1):
dp[i + v] = max(dp[i+v], dp[i] + p)
print(dp[20])
С помощью волшебного бинарного представления мы вернули задачу о множестве рюкзаков к задаче о рюкзаке с нулем 1. Надо сказать, что это действительно волшебство. ноДвоичная запись — не единственное решение, мы также можем решить эту задачу без двоичного кода. Это включает в себя совершенно новый метод, который мы изучим с вами в следующей статье из-за нехватки места.
На сегодняшней статье про несколько рюкзаков и полных рюкзаков все, если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.