Bonjour,
je travaille sur le problème du sac à dos (knapsack). Je suis actuellement sur une première ébauche de mon heuristique glouton, j'arrive à le compiler, cependant il ne renvoie pas les résultats attendus, et impossible d'afficher (cout) mes vecteurs pour voir où ça bloque
Voici mon code:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 #include<iostream> #include<fstream> #include<string> #include<vector> using namespace std; struct Objet{ int i; int wi; int pi; }; struct Instance{ int capacite; Objet vec; }; struct Solution{ int ps; }; Instance lecture(){ int taille; string filename; Instance I; cout << "Entrez le nom du fichier :" << endl; cin >> filename; ifstream inf(filename.c_str()); inf >> taille >> I.capacite >> ws; vector<Objet> vec(taille); for (int i = 0; i < taille; i++){ inf >> vec[i].wi >> vec[i].pi >> ws; vec[i].i=i; } inf.close(); return I; }Et voici le résultat :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 #include<iostream> #include<fstream> #include<string> #include<vector> #include"knapsack.h" using namespace std; void echanger(int a, int b) { int tmp = a; a = b; b = tmp; } vector<double> tri(vector<double> u){ int inversion=0; do{ for(int i=0; i<u.size(); ++i){ if(u[i]<u[i+1]){ echanger(u[i], u[i+1]); inversion=1; } } } while(inversion); return u; } int main(){ Instance I; Solution S; vector<double> u; vector<Objet> vec; lecture(); for(int i=0; i<u.size(); ++i) u[i]=vec[i].pi/vec[i].wi ; tri(u); for(int i=0;i<u.size();++i) cout << vec[i].pi ; int i=0; while ( i < I.capacite){ if (I.capacite-u[i]>=0){ S.ps=S.ps+u[i]; ++i; } else ++i; } cout << S.ps << endl; //for(int i=0;i<u.size();++i) cout << u[i] << endl; return 0; }
Merci de votre compréhension et du temps que vous m'accordez.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3Entrez le nom du fichier : Data/ks_4_0 0
Cordialement.
Partager