Оптимальный способ заполнения 2 рюкзаков?

Алгоритм динамического программирования для оптимального заполнения рюкзака хорошо работает в случае одного рюкзака. Но есть ли эффективный известный алгоритм, который будет оптимально заполнять 2 рюкзака (емкости могут быть неравными)?

Я пробовал следующие два подхода, и ни один из них не является правильным.

  • Сначала заполните первый рюкзак, используя оригинальный алгоритм DP, чтобы заполнить один рюкзак, а затем заполнить другой рюкзак.
  • Сначала заполните рюкзак размером W1 + W2, а затем разделим решение на два решения (где W1 и W2 - емкости двух ранцепов).

Заявление о проблемах (см. также Проблема с рюкзаком в Википедии):

  • Мы должны заполнить рюкзак набором элементов (каждый элемент имеет вес и значение), чтобы максимизировать значение, которое мы можем получить от предметов, имея общий вес, меньший или равный размер рюкзака.

  • Мы не можем использовать элемент несколько раз.

  • Мы не можем использовать часть элемента. Мы не можем взять часть элемента. (Каждый элемент должен быть полностью включен или нет).

Ответы

Ответ 1

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

Оригинальный рюкзак dp[i] = best profit you can obtain for weight i

for i = 1 to n do
  for w = maxW down to a[i].weight do
    if dp[w] < dp[w - a[i].weight] + a[i].gain
      dp[w] = dp[w - a[i].weight] + a[i].gain

Теперь, поскольку у нас есть два рюкзака, мы можем использовать dp[i, j] = best profit you can obtain for weight i in knapsack 1 and j in knapsack 2

for i = 1 to n do
  for w1 = maxW1 down to a[i].weight do
    for w2 = maxW2 down to a[i].weight do
      dp[w1, w2] = max
                   {
                       dp[w1, w2], <- we already have the best choice for this pair
                       dp[w1 - a[i].weight, w2] + a[i].gain <- put in knapsack 1
                       dp[w1, w2 - a[i].weight] + a[i].gain <- put in knapsack 2
                   }

Сложность времени O(n * maxW1 * maxW2), где maxW - максимальный вес, который может нести рюкзак. Обратите внимание, что это не очень эффективно, если емкости большие.

Ответ 2

Оригинальный DP предполагает, что вы отмечаете в массиве dp значения, которые вы можете получить в ранце, и обновления выполняются, следовательно, с учетом элементов.
В случае 2 рюкзаков вы можете использовать двухмерный динамический массив, поэтому dp [i] [j] = 1, когда вы можете поместить вес i в первый и вес j во второй рюкзак. Обновление аналогично оригинальному корпусу DP.

Ответ 3

Рекурсивная формула - это любой, кто смотрит:

Учитывая n элементов, таких, что элемент я имеет вес wi и значение pi. Два рюкзака обладают емкостью W1 и W2.

Для каждого 0 <= я <= n, 0 <= a <= W1, 0 <= b <= W2, обозначить M [i, a, b] максимальное значение.

для a < 0 или b < 0 - M [i, a, b] = -∞ для я = 0 или a, b = 0 - M [i, a, b] = 0

Формула: M [i, a, b] = max {M [i-1, a, b], M [i-1, a-wi, b] + pi, M [i-1, a, b-wi] + пи}

Каждое решение проблемы с элементами я имеет элемент я в рюкзаке 1, в рюкзаке 2 или ни в одном из них.