Problème du sac à dos : algorithme glouton

Bonjour,

mon compilateur m'indique une erreur au niveau de la ligne du premier cout (ligne 12). Je cherche indéfiniment l'erreur mais ne la trouve pas. Pourriez vous m'aider svp? merci d'avance.

Code:

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
46
47
48
49
50
 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
 
int main(int argc, char** argv) {
	return 0;
	int n, i, j;
	float pl, pd, pr, maxPr, maxPd;
	float poids[n], prix[n];
	int x[n];
 
 
	cout << "Combien d'objets ? " << endl;
	cin >> n;
	cout << "Quel est le poids maximum du sac ? "<< endl;
	cin >> pl;
 
	for (i = 1, i < n, i++ ) {
		cout << "Entrez le poids du colis n°: " << i << endl;
		cin >> poids[i] << endl;
		cout << "Entrez le prix du colis n° " << i << endl;
	}
 
	pd = 0;
	pr = 0;
	maxPr = 0
 
	for (j = 1, j < n, j++){
 
		for ( i= j, i < n, i++){
 
			if (pd + poids[i]] <= pl){
				x[i] = 1;
				pd = pd + poids [i];
				pr = pr + prix[i];
			}
			else {
				x[i] = 0;
				pd = pd;
				pr = pr;
			}
 
		}
		si (pr >= maxPr){
			maxPd = pd;
			maxPr = pr;
		}
	system("PAUSE");
	return EXIT_SUCCESS;
	}
}

Salut,

quand on demande de l'aide pour une erreur, le bon sens serait d'indiquer l'erreur en question :koi:
Cependant il y a plusieurs erreurs dans ce code aisément perceptibles:
- Où sont les includes ?
- Où sont les préfixes std:: ou le using namespace std; ?
- float poids[n], prix[n]; int x[n]; n'est pas une syntaxe valide en C++. C'est des VLA uniquement valables dans certaines normes du C.
- return 0; dès le début, rendant le reste de ton code caduque.
- si (pr >= maxPr){ :weird:
- Mis à part que tu utilises cout et cin, on est loin d'un code C++.

Merci pour l'aide!! Je vais changer tout ça ;)

Je n'ai pas indiqué l'erreur car je ne voyais pas où elle était. Voilà pourquoi j'ai indiqué la ligne. Enfin, si je ne me trompe pas, je suis sur la partie "débutant" du forum. Voilà pourquoi il y a peut être plusieurs erreurs grossières. J'essaye d'apprendre

Citation:

Envoyé par maxgem

Je n'ai pas indiqué l'erreur car je ne voyais pas où elle était. Voilà pourquoi j'ai indiqué la ligne.

Tu dis que le compilateur t'indique l'erreur. Un simple copier/coller suffit pour nous la communiquer :weird:

Problème du sac à dos

Bonjour,

Je suis en train de réaliser le code du problème du Sac A Dos.

J'ai compilé mon programme, sans erreur a priori. Seulement, il y a un bug lors de l'exécution. Je tente un debug. La ligne 33 (seconde partie) semble être la fautive, avec le message suivant: "segmentation fault". Je joins les trois parties de mon code. Pourriez-vous m'éclairer svp? Merci d'avance.

Code:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
include <cstdlib>
#include <iostream>
 
using namespace std;
#include "sacADos.h"
 
 
 
int main(int argc, char ** argv){
 
    int a[10];
    Noeud arbre[N_MAX_OBJETS];
    SacADos sad;
    int i;
    int gainMaxFinal;
    int code;
    int indice;
    int fils1;
    int fils2;
    int codex;
 
    cout << "Nombre d'objets ";
    cin >> sad.nbObjets;
 
    cout << "Poids du sac ";
    cin >> sad.poidsSac;
 
    for(i = 0 ; i < sad.nbObjets; i++) {
        cout << "poids de l'objet " << i+1 << " ";
        cin >> sad.pd[i];
        cout << "valeur calorifique de l'objet " << i+1 << " ";
        cin >> sad.pc[i];  
    }
    initialiserNoeudsVides (arbre, sad.nbObjets);
    remplir1erNoeud(arbre, sad);
    afficherNoeud(arbre, 0, sad.nbObjets);
    separerNoeud(arbre, sad, 0);
    afficherNoeud(arbre, 1, sad.nbObjets);    
    afficherNoeud(arbre, 2, sad.nbObjets);
 
 
	arbre[1].etatFeuille = 0;
    arbre[2].etatFeuille = 0;
 
 
    while (code == 1) {         // tant que toutes les feuiles sont vides
		determinerIndice(arbre, fils2);
    	separerNoeud(arbre, sad, indice); 
    	afficherNoeud(arbre, fils1, sad.nbObjets);
    	afficherNoeud(arbre, fils2, sad.nbObjets);
    	arbre[indice].etatFeuille = 1;
    	arbre[fils1].etatFeuille = 0;
    	arbre[fils2].etatFeuille = 0;
	}
 
 
	determinerIndice(arbre, sad.nbObjets);
	gainMaxFinal = arbre[indice].gainMax;
 
	cout << "Le gain final est : "<< gainMaxFinal;
	cout << "Les objets mis dans le sac sont : " << endl;
	for (i = 0; i < sad.nbObjets; i++){
		if (arbre[indice].etatObjet[i] == 1){
			cout << "n° : " << i+1 << endl;
		}
	}
 
	system("PAUSE");
    return EXIT_SUCCESS;
}

#

Code:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<cstdlib>
#include <iostream>
 
using namespace std;
 
#include "sacADos.h"
 
 
 
void remplir1erNoeud(Noeud arbre[N_MAX_OBJETS], SacADos sad) {
     int i;
     float somme;
 
     arbre[0].poidsRestant = sad.poidsSac;
     somme = 0.0;
     for(i =0; i < sad.nbObjets; i++) {
           arbre[0].etatObjet[i] = 2;
           somme = somme + sad.pc[i];
     }
     arbre[0].gainMax = somme;
     arbre[0].fils1 = -1;
     arbre[0].fils2 = -1;
     arbre[0].init = true;
 
}
 
void separerNoeud(Noeud arbre[N_MAX_OBJETS],SacADos sad, int noNoeud) {
     int iMeilleurObjet = 0;
     int i;
     float max, cur;
 
 
     while(arbre[noNoeud].etatObjet[iMeilleurObjet] != 2 
         || arbre[noNoeud].poidsRestant < sad.pd[iMeilleurObjet]) {
        iMeilleurObjet ++;
     }
 
     for(i = (iMeilleurObjet+1); i < sad.nbObjets; i++) {  // boucle for ??? trouver le meilleur objet
           if(arbre[noNoeud].etatObjet[i] == 2 && arbre[noNoeud].poidsRestant >= sad.pd[i]) {
                max = sad.pc[iMeilleurObjet] / sad.pd[iMeilleurObjet];
                cur = sad.pc[i] / sad.pd[i];
                if(max < cur) {
                       iMeilleurObjet = i;
                }
           }
 
 
     int fils1 = 2* noNoeud + 1;
     int fils2 = 2* noNoeud + 2;
     arbre[noNoeud].fils1 = fils1;
     arbre[noNoeud].fils2 = fils2;
     // Le premier fils
     arbre[fils1].fils1= -1;
     arbre[fils1].fils2= -1;
     arbre[fils1].init = true;
     arbre[fils1].gainMax = arbre[noNoeud].gainMax;
     for(i = 0; i < sad.nbObjets; i++) {
           arbre[fils1].etatObjet[i] =  arbre[noNoeud].etatObjet[i]; // chaque objet a le même état,
                                                               // juste petit changement après
     } 
     arbre[fils1].etatObjet[iMeilleurObjet] = 1;   // pouquoi?
     arbre[fils1].poidsRestant = arbre[noNoeud].poidsRestant - sad.pd[iMeilleurObjet];
 
     bool rempli = true;
 
     for(i = 0; i < sad.nbObjets; i++) {
           if( arbre[fils1].etatObjet[i] == 2 && sad.pd[i] < arbre[fils1].poidsRestant) {
               rempli = false;
               }
     }
     arbre[fils1].rempli = rempli;
 
     // Le deuxième fils
     arbre[fils2].fils1= -1;
     arbre[fils2].fils2= -1;
     arbre[fils2].init = true ;
     arbre[fils2].gainMax = arbre[noNoeud].gainMax - sad.pc[iMeilleurObjet];
     for(i = 0; i < sad.nbObjets; i++) {
           arbre[fils2].etatObjet[i] =  arbre[noNoeud].etatObjet[i]; // on met à jour l'état de l'objet 
           													   // à ce niveau dans le tab etatObjet
           													   // soit 0 ou 1 ou 2
     } 
     arbre[fils2].etatObjet[iMeilleurObjet] = 0;  // pourquooi ??
     arbre[fils2].poidsRestant = arbre[noNoeud].poidsRestant;
 
     rempli = true;
 
     for(i = 0; i < sad.nbObjets; i++) {
           if( arbre[fils2].etatObjet[i] == 2  && sad.pd[i] < arbre[fils2].poidsRestant) {
               rempli = false;
               }
     }
     arbre[fils2].rempli = rempli;
}
}
void afficherNoeud(Noeud arbre[N_MAX_OBJETS], int noNoeud, int nbObjets){
     int i;
     cout << "Noeud n° " << noNoeud << endl;
     cout << "Gain Max " << arbre[noNoeud].gainMax << endl;
     cout << "Poids restant " << arbre[noNoeud].poidsRestant << endl;
     if(arbre[noNoeud].rempli == true) {
        cout << "Le sac est rempli " << endl; 
     }
     else {
       cout << "Le sac n'est pas rempli " << endl; 
     }
     cout << "dans le sac, il y a " << endl;
     for(i = 0 ; i < nbObjets; i++) {   //???
           if(arbre[noNoeud].etatObjet[i] == 1) {
              cout << "objet " << i+1 << ",";
          }
     }
     cout << endl << endl;    
}
 
 
int determinerIndice (Noeud arbre[N_MAX_OBJETS], int fils2){
	int max;
	int indice;
	int i;
 
	max = 0 ;
	for (i=1 ; i < fils2; i++){
		if (arbre[i].gainMax >= max && arbre[i].etatFeuille == 0) {
			max = arbre[i].gainMax;
			indice = i;
		}
	return indice;
	}
}
 
int sacRempli (Noeud arbre[N_MAX_OBJETS], int fils2){
	int a;
	int code;
	int i;
 
 
	code = 1;
 
	for (i = 1; i < fils2; i++){
		if (arbre[i].etatFeuille == 0 && arbre[i].rempli == false) {   // si tous les noeuds sont des feuilles et qu'ils ne sont pas remplis
			a = 1;
			code = code * a;
		}			
	}
	return code;
}
 
 
void initialiserNoeudsVides(Noeud arbre[N_MAX_OBJETS],int nbObjets){
	int i;
	for(i = 0; i < nbObjets ; i++){
		arbre[i].init = false;
	}
}

Code:

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
#define N_MAX_OBJETS 100
 
typedef struct {
        int etatObjet[N_MAX_OBJETS];
        float gainMax;
        float poidsRestant;
        bool rempli;
        int fils1;
        int fils2;
        int etatFeuille;
        bool init;
 
 
} Noeud;
 
typedef struct {
        float poidsSac;
        int nbObjets;
        float pc[N_MAX_OBJETS];
        float pd[N_MAX_OBJETS];
} SacADos;
 
void remplir1erNoeud(Noeud arbre[N_MAX_OBJETS], SacADos sad);
 
void separerNoeud(Noeud arbre[N_MAX_OBJETS], SacADos sad, int noNoeud);
 
void afficherNoeud(Noeud arbre[N_MAX_OBJETS], int noNoeud, int nbObjets);
 
int determinerIndice(Noeud arbre[N_MAX_OBJETS], int nbObjets);
 
int sacRempli(Noeud arbre[N_MAX_OBJETS], int fils2);
 
void initialiserNoeudsVides(Noeud arbre[N_MAX_OBJETS],int nbObjets);

segmentation fault = j'essaie d'utiliser de la mémoire d'une mauvaise façon.
D'une manière générale, c'est que tu débordes d'un tableau ou que tu utilises un pointeur non initialisé, ou libéré (c'est la même chose).

Tu fais du C++? utilises les std::vector.
Cela te permettra d'éviter les dépassements de tableaux dans l'immense majorité des cas.
Et tu apprendras à faire les choses de la bonne façon.

Où sont les controles pour t'assurer que les tableaux sont correctement initialisés.

Tu écris dans ton main: Noeud arbre[N_MAX_OBJETS];. C'est une définition d'un tableau.
Les N_MAX_OBJETS éléments de arbre sont construits. Que valent ils? dans quel état sont-ils?

En fait, ils sont initialisés n'importe comment (constructeur par défaut), et c'est très dommage, parce qu'ils ne sont pas dans un état valide.

Ca ressemble à un sujet d'étudiant, c'est dommage qu'en fin d'année scolaire, tu en sois encore aux tableaux C en C++.