InfluencesMag.org
Home

0-1 Knapsack Using Branch-and-bound Code In C

8 min read Jun 03, 2024
0-1 Knapsack Using Branch-and-bound Code In C

Résoudre le problème du sac à dos 0-1 à l'aide de la méthode Branch and Bound en C

Le problème du sac à dos 0-1 est un problème classique d'optimisation combinatoire. Il consiste à trouver le sous-ensemble optimal d'objets à mettre dans un sac à dos, en maximisant la valeur totale des objets sélectionnés, sous la contrainte de respecter une capacité de poids maximale.

La méthode Branch and Bound est une technique de recherche efficace pour résoudre des problèmes d'optimisation combinatoire. Elle fonctionne en explorant l'espace de recherche de manière systématique, en utilisant des bornes supérieures et inférieures pour éliminer des branches de l'arbre de recherche qui ne contiennent pas de solutions optimales.

Code C pour résoudre le problème du sac à dos 0-1 à l'aide de la méthode Branch and Bound

Voici un exemple de code C pour résoudre le problème du sac à dos 0-1 à l'aide de la méthode Branch and Bound :

#include 
#include 

// Structure pour représenter un objet
struct Objet {
  int valeur;
  int poids;
};

// Fonction pour calculer la borne supérieure
int borneSup(struct Objet objets[], int n, int W, int wTotal, int vTotal) {
  // Si le poids total dépasse la capacité du sac à dos, renvoyer 0
  if (wTotal > W) {
    return 0;
  }
  // Calculer la valeur totale des objets restants en supposant que tous les objets peuvent être inclus
  int valeurRestante = 0;
  for (int i = n; i < n; i++) {
    valeurRestante += objets[i].valeur;
  }
  // Retourner la somme de la valeur totale actuelle et de la valeur totale restante
  return vTotal + valeurRestante;
}

// Fonction récursive pour résoudre le problème du sac à dos 0-1 à l'aide de la méthode Branch and Bound
int sacADos(struct Objet objets[], int n, int W, int wTotal, int vTotal, int *meilleureValeur) {
  // Cas de base : si tous les objets ont été traités, renvoyer la valeur totale actuelle
  if (n == 0) {
    *meilleureValeur = vTotal;
    return vTotal;
  }

  // Calculer la borne supérieure
  int borne = borneSup(objets, n, W, wTotal, vTotal);

  // Si la borne supérieure est inférieure à la meilleure valeur actuelle, ne pas poursuivre la recherche
  if (borne < *meilleureValeur) {
    return *meilleureValeur;
  }

  // Branche gauche : inclure l'objet actuel
  int inclure = sacADos(objets, n - 1, W, wTotal + objets[n - 1].poids, vTotal + objets[n - 1].valeur, meilleureValeur);

  // Branche droite : exclure l'objet actuel
  int exclure = sacADos(objets, n - 1, W, wTotal, vTotal, meilleureValeur);

  // Retourner la meilleure valeur parmi les deux branches
  return (inclure > exclure) ? inclure : exclure;
}

int main() {
  int n, W;
  printf("Entrez le nombre d'objets : ");
  scanf("%d", &n);
  printf("Entrez la capacité du sac à dos : ");
  scanf("%d", &W);

  struct Objet objets[n];
  printf("Entrez la valeur et le poids de chaque objet :\n");
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &objets[i].valeur, &objets[i].poids);
  }

  int meilleureValeur = INT_MIN;
  int valeurOptimale = sacADos(objets, n, W, 0, 0, &meilleureValeur);

  printf("La meilleure valeur possible est : %d\n", valeurOptimale);

  return 0;
}

Explication du code

  1. Structure Objet: La structure Objet stocke la valeur et le poids de chaque objet.

  2. Fonction borneSup: Cette fonction calcule la borne supérieure, qui représente la valeur maximale que l'on peut obtenir en incluant tous les objets restants dans le sac à dos, en supposant que le poids total ne dépasse pas la capacité du sac.

  3. Fonction sacADos: Cette fonction est la fonction récursive principale qui implémente l'algorithme Branch and Bound. Elle prend en entrée un tableau d'objets, la capacité du sac à dos, le poids total des objets déjà inclus, la valeur totale des objets déjà inclus, et un pointeur vers la meilleure valeur trouvée jusqu'à présent.

  4. Cas de base: Si tous les objets ont été traités, la fonction renvoie la valeur totale actuelle.

  5. Calcul de la borne supérieure: La fonction calcule la borne supérieure en utilisant la fonction borneSup.

  6. Elimination des branches: Si la borne supérieure est inférieure à la meilleure valeur actuelle, la fonction arrête la recherche sur cette branche, car il est impossible de trouver une solution meilleure que celle qui est déjà trouvée.

  7. Exploration des branches: La fonction explore deux branches : une branche où l'objet actuel est inclus dans le sac à dos et une branche où il est exclu.

  8. Renvoi de la meilleure valeur: La fonction renvoie la meilleure valeur parmi les deux branches explorées.

  9. Fonction main: Cette fonction lit les données d'entrée, appelle la fonction sacADos pour résoudre le problème, et affiche la meilleure valeur trouvée.

Conclusion

La méthode Branch and Bound est une approche efficace pour résoudre le problème du sac à dos 0-1. Le code C présenté ci-dessus illustre la mise en œuvre de cette méthode. En utilisant des bornes supérieures et inférieures, cette méthode permet d'éliminer des branches de l'arbre de recherche qui ne contiennent pas de solutions optimales, ce qui accélère considérablement la recherche.

Related Post

Featured Posts