Résoudre le problème du sac à dos 0/1 en utilisant la programmation dynamique en Java
Le problème du sac à dos 0/1 est un problème classique d'optimisation combinatoire. Le problème est de trouver la meilleure sélection d'objets à placer dans un sac à dos, étant donné que chaque objet a un poids et une valeur, et que le sac à dos a une capacité de poids donnée. Le but est de maximiser la valeur totale des objets dans le sac à dos.
Comprendre le problème
Imaginez que vous êtes un voleur et que vous avez trouvé un sac à dos. Vous avez une collection d'objets précieux à choisir, chacun ayant une valeur et un poids. Le sac à dos a une capacité de poids limitée. Votre objectif est de choisir les objets les plus précieux qui s'adaptent à votre sac à dos. Vous ne pouvez pas prendre une partie d'un objet, vous devez le prendre en entier ou le laisser (d'où le nom "0/1").
Programmation dynamique en Java
La programmation dynamique est une approche efficace pour résoudre le problème du sac à dos 0/1. Elle fonctionne en construisant une table qui stocke les solutions optimales pour tous les sous-problèmes possibles. La table est indexée par le poids et les objets. Chaque entrée de la table représente la valeur maximale pouvant être obtenue avec un poids donné en utilisant un ensemble d'objets donné.
Voici un exemple de code Java pour résoudre le problème du sac à dos 0/1 en utilisant la programmation dynamique :
public class Knapsack {
public static int knapsack(int[] poids, int[] valeurs, int capacité) {
int n = poids.length;
int[][] dp = new int[n + 1][capacité + 1];
// Initialisation de la table dp
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacité; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (poids[i - 1] <= w) {
dp[i][w] = Math.max(valeurs[i - 1] + dp[i - 1][w - poids[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
// La valeur maximale se trouve dans le dernier élément de la table dp
return dp[n][capacité];
}
public static void main(String[] args) {
int[] poids = {10, 20, 30};
int[] valeurs = {60, 100, 120};
int capacité = 50;
int valeurMax = knapsack(poids, valeurs, capacité);
System.out.println("La valeur maximale du sac à dos est : " + valeurMax);
}
}
Explication du code
-
Initialisation de la table dp: La première étape consiste à initialiser la table dp avec des zéros. La première ligne et la première colonne de la table sont initialisées à zéro, car la valeur maximale avec un poids ou un nombre d'objets égal à zéro est toujours zéro.
-
Itération sur les objets: Le code itère sur tous les objets, en partant de l'objet 1. Pour chaque objet, le code itère sur toutes les capacités possibles du sac à dos, en partant de la capacité 1.
-
Calcul de la valeur maximale: Pour chaque objet et chaque capacité, le code calcule la valeur maximale qui peut être obtenue en incluant ou en excluant l'objet actuel. Si le poids de l'objet actuel est inférieur ou égal à la capacité du sac à dos, la valeur maximale est le maximum entre la valeur de l'objet actuel plus la valeur maximale qui peut être obtenue avec le reste de la capacité du sac à dos (en utilisant les objets précédents), et la valeur maximale qui peut être obtenue sans l'objet actuel (en utilisant les objets précédents). Si le poids de l'objet actuel est supérieur à la capacité du sac à dos, la valeur maximale est la valeur maximale qui peut être obtenue sans l'objet actuel (en utilisant les objets précédents).
-
Retour de la valeur maximale: Une fois que le code a terminé d'itérer sur tous les objets et toutes les capacités, la valeur maximale qui peut être obtenue se trouve dans la dernière cellule de la table dp, qui correspond à la valeur maximale pour 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. L'approche de la programmation dynamique fonctionne en construisant une table qui stocke les solutions optimales pour tous les sous-problèmes possibles. Le code Java fourni dans cet article est un exemple de la façon dont la programmation dynamique peut être utilisée pour résoudre le problème du sac à dos 0/1.
Mots clés: problème du sac à dos 0/1, programmation dynamique, Java