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

Détermination des éléments dans une solution optimale de sac à dos

L'algorithme du sac à dos, une solution au problème d'emballage des bacs NP-hard, calcule la valeur optimale valeur pouvant être obtenue à partir d’un ensemble d’éléments de capacité limitée. Cependant, les utilisateurs se demandent souvent quels éléments spécifiques contribuent à cette solution optimale.

Pour résoudre ce problème, nous pouvons modifier l'algorithme du sac à dos pour suivre les éléments sélectionnés lors du processus d'optimisation. Cela fournit un moyen direct d'identifier les éléments qui composent la solution optimale, plutôt que de se fier uniquement à la valeur de la solution.

Approche :

1. Créer une matrice sélectionnée, où selected[w][j] indique si l'élément à l'index j-1 a été sélectionné à la capacité w.
2. Initialisez la matrice sélectionnée pour 0.
3. Pendant l'algorithme du sac à dos, lors de la mise à jour de dp[w][j], définissez également selected[w][j] sur 1 si items[j-1] est choisi (dp[w][j ] = dp[w - items[j-1].getWeight()][j-1] items[j-1].getWeight()) pour indiquer que cet élément a été sélectionné.
4. Après avoir déterminé l'optimal valeur, tracez la matrice sélectionnée pour identifier les éléments spécifiques qui ont été sélectionnés.

Pseudocode :

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));
    std::vector<std::vector<int>> selected(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
                selected[w][j] = (dp[w][j] != dp[w][j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }

    // Identify selected items
    std::vector<int> takenItems;
    int line = W;
    int i = n;
    while (i > 0) {
      if (selected[line][i]) {
        takenItems.push_back(items[i-1].getIndex()); // Index of item taken
        line -= items[i-1].getWeight();
      }
      i--;
    }

    return dp[W][n];
}

Cet algorithme de sac à dos amélioré permet l'identification de non seulement la valeur optimale mais aussi les éléments spécifiques qui contribuent à cette solution optimale.

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!