Eine Speicherplatzoptimierung für den dynamischen 0/1 Rucksack-Programmieralgorithmus besteht in der Verwendung eines 1-d-Arrays (z. B. A) mit einer Größe, die der Kapazität des Rucksacks entspricht. und überschreiben Sie einfach A [w] (falls erforderlich) bei jeder I-Wiederholung, wobei A [w] den Gesamtwert angibt, wenn die ersten i Elemente betrachtet werden und die Kapazität des Rucksacks w ist. Wenn diese Optimierung verwendet wird, gibt es eine Möglichkeit, die Liste der ausgewählten Elemente zu rekonstruieren, etwa indem bei jeder Iteration des DP-Algorithmus einige zusätzliche Informationen gespeichert werden? Zum Beispiel kann im Bellman Ford Algorithm eine ähnliche Raumoptimierung implementiert werden, und der kürzeste Pfad kann immer noch rekonstruiert werden, solange wir eine Liste der Vorgängerzeiger führen, dh den letzten Sprung (oder zuerst, abhängig davon, ob eine Quelle/Zielorientierter Algorithmus wird geschrieben).Rekonstruieren der Liste von Elementen aus einer platzoptimierten 0/1 Rucksackimplementierung
Hier ist meine C++ - Funktion für das 0/1 Rucksack Problem mit dynamischen Programmierung, wo ich einen 2-d-Vektor und so dass ans [i] [j] den Gesamtwert unter Berücksichtigung der ersten i-Elemente und Rucksackkapazität j. Ich rekonstruiere den durch reverse Laufen dieses Vektor am kommissionierten Artikel:
void knapsack(vector<int> v,vector<int>w,int cap){
//v[i]=value of item i-1
//w[i]=weight of item i-1, cap=knapsack capacity
//ans[i][j]=total value if considering 1st i items and capacity j
vector <vector<int> > ans(v.size()+1,vector<int>(cap+1));
//value with 0 items is 0
ans[0]=vector<int>(cap+1,0);
//value with 0 capacity is 0
for (uint i=1;i<v.size()+1;i++){
ans[i][0]=0;
}
//dp
for (uint i=1;i<v.size()+1;i++) {
for (int x=1;x<cap+1;x++) {
if (ans[i-1][x]>=ans[i-1][x-w[i-1]]+v[i-1]||x<w[i-1])
ans[i][x]=ans[i-1][x];
else {
ans[i][x]=ans[i-1][x-w[i-1]]+v[i-1];
}
}
}
cout<<"Total value: "<<ans[v.size()][cap]<<endl;
//reconstruction
cout<<"Items to carry: \n";
for (uint i=v.size();i>0;i--) {
for (int x=cap;x>0;x--) {
if (ans[i][x]==ans[i-1][x]) //item i not in knapsack
break;
else if (ans[i][x]==ans[i-1][x-w[i-1]]+v[i-1]) { //item i in knapsack
cap-=w[i-1];
cout<<i<<"("<<v[i-1]<<"), ";
break;
}
}
}
cout<<endl;
}
Ich bin ein bisschen verwirrt über die Frage; Sie beschreiben einen eindimensionalen Zustandsraum "A", aber die Implementierung verwendet einen zweidimensionalen Zustandsraum "ans"? Also verwendet im Grunde die _space_optimized_ Implementierung auch 'ans', sondern verwirft die Zeilen für kleinere Werte von' i'? – Codor
@Codor Richtig, ich zeige nur, wie wir die Liste der Elemente aus einem 2-d-Vektor rekonstruieren. Ich weiß nicht, wie wir es machen, wenn es ein 1-d-Vektor ist. Die Berechnung nur des Gesamtwerts mit diesem 1-d-Vektor ist jedoch einfach, wir hätten einfach ans [x] anstelle von ans [i] [x] und überschreiben ans [x]. Wenn Element i nicht enthalten ist, bleibt ans [x] für die Iteration unverändert, andernfalls ersetzen wir es durch ans [i] + v [i-1]. – kabir