Comment puis-je récupérer les éléments spécifiques inclus dans la solution optimale de l'algorithme Knapsack ?

Récupération d'éléments de l'algorithme Knapsack

L'algorithme Knapsack détermine efficacement la valeur optimale pouvant être obtenue à partir d'un ensemble d'éléments avec des contraintes. Cependant, il ne fournit que la valeur totale sans préciser quels éléments y contribuent.

Pour obtenir les éléments spécifiques inclus dans la solution optimale, suivez ces étapes dans l'algorithme :

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
        }
    }
}

Ceci Cette étape compare la valeur actuelle avec les précédentes, identifiant le moment où un élément a été ajouté à la solution. Un élément choisi fait la différence entre des valeurs consécutives égales à son poids.

Alternativement, une fois l'algorithme exécuté, vous pouvez parcourir la matrice à l'envers pour déterminer les éléments sélectionnés :

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--;

Cette approche récupère efficacement les éléments contribuant à la solution optimale, offrant ainsi un aperçu plus complet de la solution du problème.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!