Comment utiliser l'algorithme du problème du sac à dos en C++

Comment utiliser l'algorithme du problème du sac à dos en C++

Le problème du sac à dos est l'un des problèmes classiques des algorithmes informatiques. Il implique comment sélectionner certains éléments à mettre dans le sac à dos en fonction d'une capacité donnée du sac à dos, de sorte que le total soit atteint. maximiser la valeur des articles. Cet article présentera en détail comment utiliser l'algorithme de programmation dynamique en C++ pour résoudre le problème du sac à dos et donnera des exemples de code spécifiques.

Tout d'abord, nous devons définir l'entrée et la sortie du problème du sac à dos. L'entrée inclut le tableau de poids wt[] de l'article, le tableau de valeurs val[] de l'article et la capacité W du sac à dos. Le résultat consiste à choisir les articles à mettre dans le sac à dos pour maximiser la valeur. Il est défini comme suit :

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

Dans le code ci-dessus, nous utilisons un tableau bidimensionnel dp[][] pour représenter la table de transition d'état de la programmation dynamique, où dpi représente la sélection des i premiers éléments et la capacité du sac à dos est j Valeur totale maximale. L'algorithme spécifique est implémenté comme suit :

1. Initialisez la première ligne et la première colonne du tableau bidimensionnel dp[][] à 0, indiquant qu'il n'y a aucun élément parmi lequel choisir ou la valeur totale maximale lorsque la capacité est de 0 est 0 ;

2. From À partir de la ligne 1 et de la colonne 1, calculez chaque dpi :

   • Si le poids de l'article actuel wt[i-1] est inférieur ou égal à la capacité du sac à dos j, vous pouvez choisir de mettre l'article ou ne pas y mettre l'article. Sélectionnez la valeur totale la plus élevée dans la situation
   • Si le poids de l'article actuel wt[i-1] est supérieur à la capacité du sac à dos j, l'article actuel ne peut pas être mis ; in, et la valeur totale est égale à l'état précédent, c'est-à-dire dpi-1 ;
3. Finally Renvoie dpn, qui représente la valeur totale maximale lors de la sélection parmi les n premiers éléments et la capacité du sac à dos est W.

Ce qui suit est un exemple de code utilisant l'algorithme du problème du sac à dos :

#include 
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

int main() {
   int val[] = {60, 100, 120};
   int wt[] = {10, 20, 30};
   int W = 50;
   int n = sizeof(val) / sizeof(val[0]);
   cout << "最大总价值为：" << knapSack(W, wt, val, n) << endl;
   return 0;
}

Exécutez le code ci-dessus et la valeur totale maximale du résultat de sortie est de 220, ce qui signifie que lorsque la capacité du sac à dos est de 50, la valeur maximale qui peut être obtenu en sélectionnant la valeur totale des éléments 1 et 3.

En plus des méthodes de programmation dynamique ci-dessus, le problème du sac à dos peut également être résolu en utilisant d'autres méthodes telles que le retour en arrière et les algorithmes gloutons. Ce qui précède est une introduction détaillée sur la façon dont nous utilisons l'algorithme du problème du sac à dos en C++. J'espère que cela vous sera utile.

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!