Wie können wir effizient bestimmen, welche Artikel in der optimalen Rucksacklösung enthalten sind?

Bestimmen von Elementen in der optimalen Knapsack-Lösung

Der angegebene Knapsack-Algorithmus berechnet effizient den optimalen Wert für das Bin-Packing-Problem. Die Aufgabe besteht jedoch darin, die Elemente zu identifizieren, die diese optimale Lösung ausmachen.

1. Verfolgen der Auswahl:

Nachdem wir den optimalen Wert in der dp-Matrix berechnet haben, können wir zurückverfolgen, um die ausgewählten Elemente zu bestimmen.

dp_copy = dp;  // Copy the dp matrix for backtracking

int weight_idx = W;
int item_idx = n;

while (weight_idx > 0 && item_idx > 0):
    if dp_copy[weight_idx][item_idx] != dp_copy[weight_idx - items[item_idx - 1].getWeight()][item_idx - 1]:
        // Element 'item_idx' is included in the optimal solution
        weight_idx -= items[item_idx - 1].getWeight()
        item_idx -= 1

2. Pseudocode-Interpretation:

• Wir durchlaufen die dp-Matrix in umgekehrter Reihenfolge von der letzten Zelle zur ersten.
• Wir prüfen, ob der Unterschied zwischen der aktuellen Zelle und Die Zelle darüber und links in der Matrix entspricht der Gewichtung des entsprechenden Elements.
• Wenn dies der Fall ist, wird das mit diesem Zellenwert verknüpfte Element in die einbezogen Lösung.
• Wir passen den Gewichtsindex und den Artikelindex entsprechend an, um einen weiteren Rückschritt durchzuführen.

3. Komplexität:

Dieser Backtracking-Ansatz erfordert O(W * n) Zeitkomplexität, wobei W die Beutelkapazität und n die Anzahl der Artikel ist. Es durchläuft jede Zelle in der Matrix einmal und führt eine zeitkonstante Suchoperation durch.

Das obige ist der detaillierte Inhalt vonWie können wir effizient bestimmen, welche Artikel in der optimalen Rucksacklösung enthalten sind?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!