Inkrementelles Berechnen des Rucksacks

Question

Gibt es eine Möglichkeit, das Rucksackproblem inkrementell zu berechnen? Irgendein Annäherungsalgorithmus? Ich versuche das Problem im folgenden Szenario zu lösen.

Sei D mein Datensatz, der nicht bestellt ist und nicht sein sollte. D ist in 3 Teilmengen unterteilt, nämlich D1, D2 und D3. D1, D2 und D3 können je nach Bedarf bestellt werden. Ich möchte separate Rucksacklösungen für Sets (D1, D2) und (D2, D3) berechnen, aber ich möchte nicht vermeiden, D2 zweimal zu berechnen. Also, im Grunde möchte ich:

• Compute (D2) // eine Operation tun
• speichern es als Zwischenergebnis
• es mit D1 verwenden und Ranzen Ergebnis (D1, D2)
erhalten
• es mit D3 verwenden und Ranzen Ergebnis (D2, D3)

diese Weise die Daten Traversal über D2 erfolgt nur einmal erhalten. Gibt es eine Möglichkeit, den Rucksack inkrementell so zu lösen?

Answer 1

Wikipedia gibt diesen Pseudo-Code für 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]) 

Dies baut ein 2-dimensionales Array, so dass m[n, W] (das letzte Element in der letzten Reihe) ist die Lösung - Sie führen dies auf D2 .

Dann schreiben Sie einen anderen Algorithmus, der dieses Array als Eingabe und

1. nicht tut, nimmt den for j ... Teil um das Array zu initialisieren
2. Hat for i from D2.count+1 to (D2.count + other.count) do: zu beginnen, wo der andere aufhörte. (Sie müssen i anpassen, wenn Sie in den Arrays w und v nachschauen)