Maison > développement back-end > C++ > Comment pouvons-nous déterminer efficacement les éléments inclus dans la solution optimale de sac à dos ?

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

Susan Sarandon
Libérer: 2024-12-10 07:47:16
original
405 Les gens l'ont consulté

How Can We Efficiently Determine the Items Included in the Optimal Knapsack Solution?

É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
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal