Интенсивный вычислительный рюкзак

Question

Есть ли способ вычислить проблему с рюкзаком постепенно? Любой алгоритм аппроксимации? Я пытаюсь решить проблему в следующем сценарии.

Позвольте D быть моим набором данных, который не упорядочен и не должен быть. D делится на 3 подмножества, а именно D1, D2 и D3. D1, D2 и D3 могут быть заказаны, если необходимо. Я хочу вычислить отдельные решения для ранца для множеств (D1, D2) и (D2, D3), но я не хочу, чтобы дважды вычислить D2. Так, в принципе, я хочу:

• вычисления (D2) // сделать некоторые операции
• сохранить его как промежуточный результат
• использовать его с D1 и получить результат рюкзака для (D1, D2)
• использовать его с D3 и получить результат рюкзака для (D2, D3)

Таким образом, обход данных через D2 производятся только один раз. Есть ли способ поэтапно разрешить рюкзак?

Answer 1

Википедия дает этот псевдокод 0/1 рюкзаке: https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem

// Input: 
// Values (stored in array v) 
// Weights (stored in array w) 
// Number of distinct items (n) 
// Knapsack capacity (W) 

for j from 0 to W do: 
    m[0, j] := 0 

for i from 1 to n do: 
    for j from 0 to W do: 
     if w[i-1] > j then: 
      m[i, j] := m[i-1, j] 
     else: 
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1]) 

Это строит 2 одномерный массив такой, что m[n, W] (последний элемент в последней строке) является решение - запустить это на D2 ,

Затем вы пишете другой алгоритм, который принимает этот массив в качестве входных данных и

1. Не делать for j ... части для инициализации массива
2. ли for i from D2.count+1 to (D2.count + other.count) do:, чтобы начать, когда другие один кончил. (вам нужно настроить i при поиске в массивах w и v)