0-1 Knapsack Code In C++

7 min read Jun 03, 2024

Le problème du sac à dos 0-1 en C++ : Une solution efficace

Le problème du sac à dos 0-1 est un problème classique en informatique qui implique la maximisation de la valeur des objets qui peuvent être placés dans un sac à dos de capacité limitée. Dans ce problème, vous avez un ensemble d'objets, chacun avec un poids et une valeur, et un sac à dos avec une capacité de poids maximale. Le but est de sélectionner les objets à mettre dans le sac à dos afin de maximiser la valeur totale, sans dépasser la capacité du sac à dos.

Comprendre l'approche

L'approche la plus courante pour résoudre le problème du sac à dos 0-1 est la programmation dynamique. Cette approche utilise un tableau pour stocker les solutions optimales pour les sous-problèmes. Le tableau est indexé par la capacité du sac à dos et le nombre d'objets considérés. Chaque cellule du tableau contient la valeur maximale que l'on peut obtenir en utilisant les objets jusqu'à cet index avec la capacité du sac à dos correspondante.

Code C++ pour le problème du sac à dos 0-1

#include 
#include 

using namespace std;

int knapsack(int capacity, const vector& values, const vector& weights, int n) {
  // Créer un tableau pour stocker les solutions optimales
  vector> dp(n + 1, vector(capacity + 1, 0));

  // Remplir le tableau de manière itérative
  for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        // Si l'objet actuel peut tenir dans le sac à dos
        // prendre le maximum entre l'inclure ou non
        dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
      } else {
        // Si l'objet actuel ne peut pas tenir dans le sac à dos
        // prendre la valeur de la solution précédente
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  // La valeur maximale est stockée dans la dernière cellule du tableau
  return dp[n][capacity];
}

int main() {
  // Valeurs des objets
  vector values = {60, 100, 120};
  // Poids des objets
  vector weights = {10, 20, 30};
  // Capacité du sac à dos
  int capacity = 50;

  // Nombre d'objets
  int n = values.size();

  // Résoudre le problème du sac à dos 0-1
  int maxValue = knapsack(capacity, values, weights, n);

  // Afficher la valeur maximale
  cout << "La valeur maximale du sac à dos est : " << maxValue << endl;

  return 0;
}

Explication du code

Le code commence par inclure les en-têtes nécessaires et définir l'espace de noms std.
La fonction knapsack prend en entrée la capacité du sac à dos, les valeurs et les poids des objets et le nombre d'objets.
Un tableau 2D dp est créé pour stocker les solutions optimales pour les sous-problèmes. La première ligne et la première colonne du tableau sont initialisées à zéro.
Le code utilise deux boucles imbriquées pour remplir le tableau dp de manière itérative. La première boucle itère sur tous les objets et la deuxième boucle itère sur toutes les capacités du sac à dos possibles.
Pour chaque cellule dp[i][w], le code vérifie si l'objet actuel peut tenir dans le sac à dos avec la capacité w.
Si l'objet actuel peut tenir, le code prend le maximum entre l'inclure dans le sac à dos ou non.
Si l'objet actuel ne peut pas tenir, le code prend la valeur de la solution précédente dp[i - 1][w].
La valeur maximale est stockée dans la dernière cellule du tableau dp[n][capacity].
La fonction main crée un exemple de jeu de données pour les valeurs, les poids et la capacité du sac à dos.
La fonction knapsack est appelée avec ces données et la valeur maximale obtenue est affichée.

Conclusion

Le code C++ présenté ci-dessus est une solution efficace pour le problème du sac à dos 0-1. Il utilise la programmation dynamique pour trouver la solution optimale. Le code est facile à comprendre et à modifier pour différentes entrées.