Wie kann ich die spezifischen Elemente abrufen, die in der optimalen Lösung des Knapsack-Algorithmus enthalten sind?

Elemente aus dem Knapsack-Algorithmus abrufen

Der Knapsack-Algorithmus ermittelt effizient den optimalen Wert, der aus einer Reihe von Elementen mit Einschränkungen erreichbar ist. Es wird jedoch nur der Gesamtwert bereitgestellt, ohne anzugeben, welche Elemente dazu beitragen.

Um die spezifischen Elemente zu erhalten, die in der optimalen Lösung enthalten sind, befolgen Sie diese Schritte innerhalb des Algorithmus:

for (size_t j = 1; j <= n; j++)
{
    for ( int w = 1; w <= W; w++)
    {
        ...
        if (dp[w][j] != dp[w][j-1] && dp[w][j] == dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight())
        {
            // Mark element 'j' as included in the solution
        }
    }
}

Dies Schritt vergleicht den aktuellen Wert mit den vorherigen und erkennt, wann ein Element zur Lösung hinzugefügt wurde. Ein ausgewähltes Element macht die Differenz zwischen aufeinanderfolgenden Werten gleich seiner Gewichtung.

Alternativ können Sie nach Ausführung des Algorithmus die Matrix in umgekehrter Reihenfolge durchlaufen, um die ausgewählten Elemente zu bestimmen:

int line = W;
int i = n;
while (i > 0):
    if (dp[line][i] - dp[line - weight(i)][i-1] == item[i].getValue()):
        // Item 'i' is in the solution
        i--;
        line -= weight(i);
    else:
        i--;

Dieser Ansatz ruft effizient die Elemente ab, die zur optimalen Lösung beitragen, und bietet so einen umfassenderen Einblick in die Lösung des Problems.

Das obige ist der detaillierte Inhalt vonWie kann ich die spezifischen Elemente abrufen, die in der optimalen Lösung des Knapsack-Algorithmus enthalten sind?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!