0 1 Knapsack C++

7 min read Jun 02, 2024

Le problème du sac à dos 0/1 en C++

Le problème du sac à dos 0/1 est un problème classique en optimisation combinatoire. Il s'agit de déterminer la manière optimale de remplir un sac à dos avec un ensemble d'objets, étant donné que chaque objet a une valeur et un poids. L'objectif est de maximiser la valeur totale des objets dans le sac à dos, sans dépasser la capacité de charge du sac.

Description du problème

Dans le problème du sac à dos 0/1, vous avez un sac à dos avec une capacité maximale de charge. Vous avez également un ensemble d'objets, chacun avec un poids et une valeur. Vous devez décider quels objets mettre dans le sac à dos afin de maximiser la valeur totale des objets dans le sac, sans dépasser la capacité de charge.

La contrainte du problème est que vous ne pouvez prendre un objet qu'une seule fois (0/1). Vous ne pouvez pas prendre une partie d'un objet.

Résolution du problème en C++

L'approche la plus courante pour résoudre le problème du sac à dos 0/1 est la programmation dynamique. Cette approche consiste à construire une table qui stocke les solutions optimales pour tous les sous-problèmes possibles. La table est indexée par la capacité du sac à dos et le nombre d'objets considérés.

Voici un exemple de code C++ pour résoudre le problème du sac à dos 0/1 en utilisant la programmation dynamique :

#include 
#include 

using namespace std;

// Fonction pour résoudre le problème du sac à dos 0/1
int knapsack(int W, const vector& wt, const vector& val, int n) {
  // Créer une table pour stocker les solutions optimales
  vector> dp(n + 1, vector(W + 1, 0));

  // Remplissage de la table
  for (int i = 1; i <= n; ++i) {
    for (int w = 1; w <= W; ++w) {
      // Si le poids de l'objet courant est inférieur ou égal à la capacité du sac à dos
      if (wt[i - 1] <= w) {
        // Calculer la valeur maximale en incluant ou en excluant l'objet courant
        dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
      } else {
        // Si le poids de l'objet courant est supérieur à la capacité du sac à dos
        // La valeur maximale est la même que celle du sous-problème précédent
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  // La valeur maximale est stockée dans dp[n][W]
  return dp[n][W];
}

int main() {
  // Définir les poids et les valeurs des objets
  vector wt = {10, 20, 30};
  vector val = {60, 100, 120};
  int W = 50; // Capacité du sac à dos
  int n = wt.size(); // Nombre d'objets

  // Résoudre le problème du sac à dos 0/1
  int max_value = knapsack(W, wt, val, n);

  // Afficher la valeur maximale
  cout << "La valeur maximale est : " << max_value << endl;

  return 0;
}

Explication du code

Le code C++ ci-dessus utilise une approche de programmation dynamique pour résoudre le problème du sac à dos 0/1.

La fonction knapsack() prend en entrée la capacité du sac à dos W, les poids des objets wt, les valeurs des objets val et le nombre d'objets n.
La fonction crée une table dp de dimension (n+1) x (W+1).
Chaque entrée dp[i][w] représente la valeur maximale que l'on peut obtenir en utilisant les i premiers objets et en utilisant une capacité du sac à dos de w.
La table dp est remplie de manière itérative, en utilisant la relation de récurrence suivante :

dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])

La valeur finale dans dp[n][W] représente la valeur maximale que l'on peut obtenir en utilisant tous les objets et la capacité maximale du sac à dos.

Conclusion

Le problème du sac à dos 0/1 est un problème classique d'optimisation combinatoire qui peut être résolu efficacement en utilisant la programmation dynamique. Le code C++ présenté dans cet article fournit un exemple de mise en œuvre de l'algorithme de programmation dynamique pour résoudre ce problème.