Leet Code: Проблемы с рюкзаком

Задний план

Задача о рюкзаке, по данным Википедии, является одной из наиболее изученных задач комбинаторной оптимизации.

Общее описание задачи о рюкзаке следующее:

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

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

В то время как некоторые вопросы в стиле Leet Code, как правило, «удалены» (мягко говоря) из области полезности в повседневной жизни, задача о рюкзаке на самом деле отражает очень реальный сценарий.

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

Я хочу сделать выбор. x_j представляет собой бинарный выбор: выбрать этот элемент или нет?
Если я выберу этот предмет, то получу ровно p_j преимуществ.
Однако, выбрав этот предмет, я заплачу w_j за свой выбор.
Я хотел бы максимизировать свою прибыль: SUM(p_j * x_j).
При соблюдении моего общего бюджета W. Соблюдение моего общего бюджета означает, что SUM(w_j * x_j) <= W.

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

При этом давайте рассмотрим некоторые варианты этой проблемы.

Варианты

Задача с ограниченным рюкзаком: в этом варианте я могу выбирать предмет только конечное количество раз.
Задача с неограниченным рюкзаком: в этом варианте я могу свободно выбирать предмет столько раз, сколько захочу.
Задача о дробном рюкзаке: в этом варианте предмет можно использовать в частичном количестве. Как можно понять при некотором анализе, эта задача не требует ранцевого подхода, поскольку оптимальное решение может быть принято жадным способом. Просто выберите элемент с самым высоким коэффициентом profit/cost.

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

Применение к задачам Leet Code

Размен монет 2: Неограниченный рюкзак

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

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

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

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

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

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

Общий псевдокод будет следующим:

for each coin in coins:
  for each amount, from 0 up to the total amount:
    if the amount is 0:
      record there as being 1 possible solution
    else:
      # Decision 1: Don't use the coin.
      record = # ways to form valid amount by excluding this coin
      # Decision 2: Use the coin
       If using the coin doesn't put me negative, get # ways to make up 
       this new amount
      
      Record the summation of # ways via these two methods
return the solution for using all coins to make up the total amount.

И код Python выглядит следующим образом.

Анализ сложности

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

Из временного анализа видно, что приведенное выше решение выполняется за квадратичное время, поскольку есть два цикла for, представляющие принятие решений по двум осям. Таким образом, временная сложность составляет: O( |coins| * amount ).

Поскольку это решение построено вокруг рекуррентного отношения, основанного на предыдущих подзадачах, мы используем таблицу запоминания, чтобы сократить время выполнения повторяющихся задач. Следовательно, по той же причине, что и в приведенном выше временном анализе, пространственная сложность составляет: O(|coins| * amount ).

Я знаю, что существует решение, в котором используется пространство O(|amount|) из-за того, что coins и amount могут существенно накладываться друг на друга.

Вывод

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

Leet Code: Проблемы с рюкзаком | Размен монет