Bonjour,
Je dois programmer la méthode de Branch and bound spécialisé pour le probème du sac à dos:
Les elements sont ranges par ordre des ui
wi
decroissant, le parcours se fait en profondeur d'abord, la
priorite de branchement est calquee sur l'heuristique gloutonne.
Pas 1. Initialisation: le sac-a-dos est vide et on a considere aucun objet.
Pas 2. Calcul de UB:
UB = l'utilite des objets deja presents dans le sac-a-dos + la valeur de la relaxation lineaire du
probleme residuel.
Si UB LB, alors le noeud est elague et on va au Pas 6.
Pas 3. Plongeon de xations a 1:
Tant que c'est possible, on met les objets dans le sac-a-dos (on les considere dans l'ordre donne).
Pas 4. Une xation a 0:
Si on n'a pas encore passe en revue tous les objets, alors l'objet en cours de consideration ne peut
pas ^etre pris dans le sac-a-dos et on retourne au Pas 2.
Pas 5. Mise a jour des LB: Les objets ont tous ete inclus ou exclus du sac-a-dos et le sac-a-dos obtenu
est realisable. Si sa valeur est ameliorative, alors on le garde en memoire.
Pas 6. Remontee (backtracking):
Si le dernier objet considere a ete mis dans le sac-a-dos, il est enleve.
On remonte jusqu'au dernier objet qui a ete mis dans le sac-a-dos.
S'il n'y en a pas, STOP.
On enleve cet objet du sac-a-dos et on retourne au Pas 3.
J'ai fait le code suivant, mais il y a une erreur, car ça donne pas le bon résultat:
#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
struct objet {
int indice;
int poids;
int utilite;
} ;
/*Trier */
bool mafonction(objet o1,objet o2){return (o1.utilite/o1.poids>o2.utilite/o2.poids);}
void trier (vector <objet> V){
std::sort (V.begin(),V.end(),mafonction) ;
}
/*Calculer la borne */
int borne(int i, int n, int W,vector<objet> V)
{
int j=i;
int Poids = 0;
int resultat = 0;
while ((j < n) && (Poids+ V[j].poids <= W))
{
Poids= Poids + V[j].poids;
resultat = resultat +V[j]. utilite;
j++;
}
if (j < n)
{
resultat= resultat + (W - Poids) * V[j].utilite/V[j].poids;
}
return resultat;
}
void BB(vector<objet> V, int W){
int i=1;
int n=3;
int C=W;
int Z=0;
int BS=99999999; int BI=0;
bool x[n] ;
bool _x[n];
for(int k=0;k<n;k++){_x[k]=x[k]=0;}
cout<<"ok";
/* etape 2 */
while(1){
BS=Z+borne( i, n, W,V);
if (BS <= BI){
/*etpae 6 */
if(x[n-1]==1){
x[n-1]=0;
Z=Z-V[n-1].utilite;
C=C+V[n-1].poids;
i=n-1;
}
while ((x[i]==0)and (i!=0 )){
cout<<"x "<<endl;
i=i-1;
if(i==0) { for(int k=0;k<n;k++){cout<<"s"<<k<<" "<<_x[k]<<endl;}
break;
}
}
if (i ==0 ) break;
x[i]=0;
Z=Z-V[i].utilite;
C=C+V[i].poids;
i=i+1;
}
else {
/* etape 3 */
while (i<=n && V[i].poids <=C)
{
x[i]=1;
Z=Z+V[i].utilite;
C=C-V[i].poids;
i=i+1;
}
/* etape 4 */
if(i<=n)
{
x[i]=0;
i=i+1;
}
/*etape 5 */
if(i>n) {
if (Z>BI) {
for(int k=1;k<n;k++)
{
_x[k]=x[k];
}
BI=Z ;
}
if(x[n]==1){
x[n]=0;
Z=Z-V[n].utilite;
C=C+V[n].poids;
i=n-1;
}
while (x[i]==0) {
i=i-1;
if(i==0) {break;}
}
if(i==0) {
for(int k=0;k<n;k++){cout<<"s"<<_x[k]<<endl;}
break;}
}
x[i]=0;
Z=Z-V[i].utilite;
C=C+V[i].poids;
i=i+1;
}
}
}
int main(){
/* Test */
objet v={1,2,8};
objet t={2,2,3};
objet u={3,3,15};
vector<objet> V;
V.push_back(v);
V.push_back(t);
V.push_back(u);
BB (V,6);
return 0;
}
Pouvez vous,m'aider à corriger le code?j'ai besoin vraiment de votre aide. Je suis débutante en Informatique et je trouve des grands difficultés.
Merci d'avance.
-----
Envoyé par Jack 
