Wie können wir die spezifischen Elemente identifizieren, die in einer optimalen Rucksacklösung enthalten sind?

Bestimmung der Elemente in einer optimalen Rucksacklösung

Der Rucksackalgorithmus, eine Lösung für das NP-Hard-Bin-Packing-Problem, berechnet die optimale Lösung Wert, der aus einer Reihe von Artikeln mit begrenzter Kapazität erzielbar ist. Benutzer fragen sich jedoch oft, welche spezifischen Elemente zu dieser optimalen Lösung beitragen.

Um dieses Problem zu beheben, können wir den Rucksack-Algorithmus ändern, um die während des Optimierungsprozesses ausgewählten Elemente zu verfolgen. Dies bietet eine direkte Möglichkeit, die Elemente zu identifizieren, die die optimale Lösung umfassen, anstatt sich ausschließlich auf den Wert der Lösung zu verlassen.

Ansatz:

1. Erstellen Sie eine zusätzliche Lösung Matrix ausgewählt, wobei selected[w][j] angibt, ob das Element am Index j-1 mit der Kapazität w ausgewählt wurde.
2. Initialisieren Sie die ausgewählte Matrix auf 0.
3. Während des Rucksackalgorithmus wird beim Aktualisieren von dp[w][j] auch selected[w][j] auf 1 gesetzt, wenn items[j-1] ausgewählt ist (dp[w][ j] = dp[w - items[j-1].getWeight()][j-1] items[j-1].getWeight()), um anzuzeigen, dass dieses Element ausgewählt wurde.
4. Nachher Bestimmen Sie den optimalen Wert und verfolgen Sie die ausgewählte Matrix, um die ausgewählten Elemente zu identifizieren.

Pseudocode:

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));
    std::vector<std::vector<int>> selected(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
                selected[w][j] = (dp[w][j] != dp[w][j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }

    // Identify selected items
    std::vector<int> takenItems;
    int line = W;
    int i = n;
    while (i > 0) {
      if (selected[line][i]) {
        takenItems.push_back(items[i-1].getIndex()); // Index of item taken
        line -= items[i-1].getWeight();
      }
      i--;
    }

    return dp[W][n];
}

Dieser verbesserte Rucksackalgorithmus ermöglicht die Identifizierung nicht nur des optimalen Werts, sondern auch der spezifischen Elemente, die zu dieser optimalen Lösung beitragen.

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