Résoudre le problème du sac à dos 0/1 à l'aide de la programmation dynamique en C++
Le problème du sac à dos 0/1 est un problème classique d'optimisation combinatoire. Il implique de choisir un sous-ensemble d'objets à partir d'un ensemble donné, où chaque objet a un poids et une valeur, afin de maximiser la valeur totale des objets choisis tout en respectant une capacité de poids maximale.
Comprendre le problème
Imaginez que vous êtes un voyageur qui essaie de remplir un sac à dos avec des objets précieux. Chaque objet a une valeur différente et un poids différent. Vous devez choisir les objets à mettre dans votre sac à dos pour maximiser la valeur totale tout en restant dans la limite de capacité de votre sac à dos.
Formalement, le problème peut être énoncé comme suit :
- Étant donné un ensemble d'objets, où chaque objet i a un poids w<sub>i</sub> et une valeur v<sub>i</sub>,
- Et une capacité de sac à dos W,
- Trouvez le sous-ensemble d'objets qui maximise la valeur totale V tout en respectant la contrainte de poids W.
La programmation dynamique pour le sac à dos 0/1
La programmation dynamique est une technique efficace pour résoudre le problème du sac à dos 0/1. L'idée est de construire un tableau qui stocke les solutions optimales pour tous les sous-problèmes possibles.
Le tableau est indexé par le poids maximum autorisé et le nombre d'objets. Chaque cellule du tableau stocke la valeur maximale qui peut être obtenue en utilisant les objets jusqu'à l'index donné, sous la contrainte de poids donnée.
L'algorithme fonctionne de manière récursive, en calculant la valeur optimale pour chaque cellule du tableau en utilisant les valeurs des cellules précédentes.
Implémentation C++
Voici une implémentation C++ de l'algorithme de programmation dynamique pour le sac à dos 0/1 :
#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 un tableau 2D pour stocker les solutions optimales
vector> dp(n + 1, vector(W + 1, 0));
// Boucle sur tous les objets
for (int i = 1; i <= n; i++) {
// Boucle sur tous les poids possibles
for (int w = 1; w <= W; w++) {
// Si le poids actuel de l'objet est supérieur au poids maximum autorisé
if (wt[i - 1] > w) {
// La valeur optimale est la même que la valeur optimale pour l'objet précédent
dp[i][w] = dp[i - 1][w];
} else {
// La valeur optimale est le maximum entre :
// 1. La valeur optimale pour l'objet précédent
// 2. La valeur de l'objet actuel + la valeur optimale pour le reste du poids
dp[i][w] = max(dp[i - 1][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]);
}
}
}
// Retourner la valeur optimale pour tous les objets et le poids maximum autorisé
return dp[n][W];
}
int main() {
// Définir le poids des objets et leur valeur
vector wt = {10, 20, 30};
vector val = {60, 100, 120};
// Définir la capacité du sac à dos
int W = 50;
// Trouver la valeur optimale
int result = knapsack(W, wt, val, wt.size());
// Afficher la valeur optimale
cout << "Valeur maximale : " << result << endl;
return 0;
}
Conclusion
La programmation dynamique offre une solution efficace pour le problème du sac à dos 0/1. L'algorithme est facile à comprendre et à mettre en œuvre, et il fournit la solution optimale pour le problème. Le code C++ donné illustre l'implémentation de cet algorithme. Vous pouvez l'utiliser comme point de départ pour résoudre des problèmes similaires d'optimisation combinatoire.