Оптимальный способ заполнения 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 или ни в одном из них.