Résoudre le problème du sac à dos 0-1 avec MATLAB
Le problème du sac à dos 0-1 est un problème d'optimisation classique qui consiste à trouver le meilleur ensemble d'objets à inclure dans un sac à dos, compte tenu de limites de poids et de valeurs. Chaque objet peut être inclus dans le sac à dos ou non (d'où le nom "0-1").
Comprendre le problème
Imaginez que vous êtes en randonnée et que vous devez choisir les objets à emporter dans votre sac à dos. Chaque objet a un poids et une valeur. Votre sac à dos a une capacité de poids limitée. Votre objectif est de maximiser la valeur totale des objets que vous emportez, tout en respectant la limite de poids.
Le code MATLAB
function [valeur_max, choix] = sac_a_dos_01(poids, valeurs, capacite)
% poids : vecteur des poids des objets
% valeurs : vecteur des valeurs des objets
% capacite : capacité de poids du sac à dos
n = length(poids);
% Matrice de programmation dynamique
M = zeros(n+1, capacite+1);
% Initialisation
for i = 1:n+1
M(i, 0) = 0;
end
for j = 1:capacite+1
M(1, j) = 0;
end
% Calculer la valeur maximale
for i = 2:n+1
for j = 1:capacite+1
if poids(i-1) <= j
M(i, j) = max(M(i-1, j), M(i-1, j-poids(i-1)) + valeurs(i-1));
else
M(i, j) = M(i-1, j);
end
end
end
% Trouver la solution optimale
valeur_max = M(n+1, capacite);
choix = zeros(1, n);
i = n;
j = capacite;
while i > 1 && j > 0
if M(i, j) != M(i-1, j)
choix(i-1) = 1;
j = j - poids(i-1);
end
i = i - 1;
end
% Afficher la solution
fprintf('Valeur maximale: %d\n', valeur_max);
fprintf('Choix des objets: %s\n', num2str(choix));
end
Comment utiliser le code
- Définir les données du problème:
poids: Un vecteur contenant les poids de chaque objet.valeurs: Un vecteur contenant les valeurs de chaque objet.capacite: La capacité de poids du sac à dos.
- Appeler la fonction:
[valeur_max, choix] = sac_a_dos_01(poids, valeurs, capacite); - Interpréter les résultats:
valeur_max: La valeur maximale que vous pouvez obtenir en remplissant le sac à dos.choix: Un vecteur indiquant quels objets sont inclus dans le sac à dos (1 = inclus, 0 = non inclus).
Exemple d'utilisation
% Données du problème
poids = [10 20 30 40];
valeurs = [60 100 120 140];
capacite = 50;
% Résoudre le problème
[valeur_max, choix] = sac_a_dos_01(poids, valeurs, capacite);
% Afficher les résultats
fprintf('Valeur maximale: %d\n', valeur_max);
fprintf('Choix des objets: %s\n', num2str(choix));
Ce code affichera:
Valeur maximale: 220
Choix des objets: 1 1 0 0
Cela signifie que la valeur maximale que vous pouvez obtenir est de 220, en incluant les objets 1 et 2 dans le sac à dos.
Conclusion
Ce code MATLAB vous permet de résoudre efficacement le problème du sac à dos 0-1. Vous pouvez l'utiliser pour trouver la meilleure solution pour diverses applications, telles que la planification de la production, la gestion de l'inventaire et l'optimisation des investissements.