Comment pouvons-nous identifier les éléments inclus dans une solution de sac à dos optimale ?

Détermination des articles dans une solution optimale pour un sac à dos

Étant donné l'algorithme Knapsack, qui emballe les articles de manière optimale pour maximiser la valeur totale, cet article aborde les aspects supplémentaires défi d'identifier les éléments spécifiques inclus dans la solution optimale.

Pour commencer, nous approfondissons le Implémentation de l'algorithme Knapsack :

int Knapsack::knapsack(std::vector<Item>& items, int W) {...}

Pour récupérer les éléments impliqués dans la solution optimale, nous pouvons exploiter les informations stockées dans la matrice calculée :

std::vector<vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));

Pseudo Code :

line = W
i = n
while (i > 0):
  if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
    // Item 'i' is in the knapsack
    i--
    line -= weight(i)
  else: 
    i--

Ce processus itératif parcourt la matrice. Lorsqu'une différence de poids correspond à la taille d'un article, cet article est considéré comme faisant partie de la solution optimale. L'article est exclu de la considération et le processus continue.

En employant cette technique, nous pouvons déterminer quels éléments constituent la combinaison la plus précieuse dans le sac à dos sans avoir besoin de stockage de données supplémentaire. Cette approche est non seulement efficace, mais fournit également des informations précieuses sur la composition optimale de la solution.

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!