Incrementally computing knapsack

Question

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario.

Let D be my data set which is not ordered and should not be. D is divided into 3 subsets, namely D1, D2 and D3. D1, D2 and D3 can each be ordered if needed. I want to compute separate knapsack solutions for sets (D1,D2) and (D2,D3), but I don't want to avoid computing D2 two times. So, basically, I want to:

• compute (D2) // do some operation
• save it as an intermediate result
• use it with D1 and get knapsack result for (D1, D2)
• use it with D3 and get knapsack result for (D2,D3)

That way the data traversal over D2 is done only once. Is there a way to solve the knapsack incrementally like this?

Answer 1

Wikipedia gives this pseudocode for 0/1 Knapsack: 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])

This builds a 2 dimensional array such that m[n, W] (the last element in the last row) is the solution -- you run this on D2.

Then you write another algorithm that takes this array as input and

1. Does not do the for j ... part to initialize the array
2. Does for i from D2.count+1 to (D2.count + other.count) do: to start where the other one left off. (you have to adjust i when looking up in the w and v arrays)