Comment pouvons-nous déterminer efficacement les éléments inclus dans la solution optimale de sac à dos ?

Éléments déterminants dans la solution optimale de sac à dos

L'algorithme de sac à dos donné calcule efficacement la valeur optimale pour le problème d'emballage des bacs. Cependant, la tâche à accomplir est d'identifier les éléments qui constituent cette solution optimale.

1. Suivi de la sélection :

Après avoir calculé la valeur optimale dans la matrice dp, nous pouvons revenir en arrière pour déterminer les éléments sélectionnés.

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. Interprétation du pseudo-code :

• Nous parcourons la matrice dp dans l'ordre inverse de la dernière cellule à la première.
• Nous vérifions si la différence entre la cellule actuelle et la cellule ci-dessus et à gauche dans la matrice est égale au poids de l'élément correspondant.
• Si c'est le cas, l'élément associé à cette valeur de cellule est inclus dans le solution.
• Nous ajustons l'indice de poids et l'indice des articles en conséquence pour revenir en arrière davantage.

3. Complexité :

Cette approche de retour en arrière nécessite une complexité temporelle O(W * n), où W est la capacité du sac et n est le nombre d'articles. Il parcourt chaque cellule de la matrice une fois et effectue une opération de recherche à temps constant.

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!