Problème du sac à dos (Knapsack)

Version imprimable

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:

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;
 
}

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
#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;
}

Et voici le résultat :

Code:

1
2
3
Entrez le nom du fichier :
Data/ks_4_0
0

Merci de votre compréhension et du temps que vous m'accordez.
Cordialement.

23/04/2018, 23h44
jo_link_noir

Tu devrais sérieusement envisager de monter le niveau de warning. Il y a au moins une variable non initialisée (I.capacite) et un overflow (for(int i=0; i<u.size(); ++i) ...u[i+1]...).

Mais le code contient beaucoup de problèmes et de points d'améliorations. En vrac:

- using namespace std; est très fortement déconseillé dans un en-tête, car son usage peut engendrer des conflits de nom.
- Depuis c++11, std::ifstream peut prendre un std::string comme type de fichier.
- Fermer le fichier à la fin de la fonction est inutile car le destructeur de std::ifstream le fait déjà.
- La fonction lecture devrait prendre un nom de fichier plutôt que de faire appel à std::cin.
- echanger n'est qu'un std::swap qui ne peut pas fonctionner. Il faut lire un cours sur les références.
- Idem pour tri qui est à remplacer par std::sort. En plus, inversion ne repasse jamais à 0 ce qui provoque une boucle infinie.
- Les valeurs booléennes se représentent avec bool et non pas un int.
- std::vector::size() retourne un std::vector::size_type, usuellement un std::size_t. Pas un nombre signé comme int.
- Les variables devraient être initialisées au moment de leur déclaration et construite au plus tard.
- C++ apporte les boucles sur intervalle: for (double x: u) std::cout << x;. Je suis persuadé que faire une boucle avec u.size().

Tout d’abord merci de votre réponse riche en enseignements.
Je tiens juste à préciser que le c++ est tout nouveau pour moi, c’est pourquoi je vous concède volontiers mon manque de rigueur.
J’ai cependant suivi votre conseil et augmenté mon niveau de warning.

Point par point :

-Il me semblait bien que «I.capacite» était initialisé à «Instance I» ? Quant à l’overflow j’ai cru résoudre le problème cependant j’obtiens une segmentation fault 11 à l’exécution du programme, est-ce lié ?
-J’utilise using namespace stp afin de rester dans le cadre du cours qui m’est fourni par la fac qui, je pense, n’est pas à jour sur tout. Bien qu’effectivement c++ 11 ait 7ans.
-Là encore j’ai rigoureusement suivi les exemples d’utilisation de ifstream de mon cours.
-idem
-Le passage par cin répond à une condition du sujet qui m’est proposé.
-j’ai donc bien remplacé par swap, quant aux références, je ne saisi pas à quelle moment celles-ci doivent intervenir.
-malgré un include<algorithm> sort ne fonctionne pas, j’ai donc corrigé ma fonction inversion.

Je m’affaire à prendre en compte vos trois derniers point d’améliorations bien que là encore pour les boucles for je m’efforce de respecter au plus près mon cours qui, très rudimentaire, n’aborde pas la notion de boucles sur intervalle.

Je vous fais parvenir la dernière version de mon code ainsi que le résultat de son exécution.
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 #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; //vec is; }; 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; }
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 #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 taille){ bool inversion; do{ for(int i=0; i<taille+1; ++i){ if(u[i]<u[i+1]){ swap(u[i], u[i+1]); inversion=1; }else inversion=0; } } while(inversion); return u; } int main(){ int taille; string filename; Instance I; Solution S; vector<double> u; vector<Objet> vec; lecture(taille, filename, I); for(int i=0; i<taille; ++i) u[i]=vec[i].pi/vec[i].wi ; tri(u,taille); //for(int i=0;i<taille;++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<taille;++i) cout << u[i] << endl; return 0; }
Code:

1 2 3 4 MacBook-Pro-de-user:DM user$ ./heuristicexe Entrez le nom du fichier : Data/ks_4_0 Segmentation fault: 11

24/04/2018, 08h15
dalfab

Citation:

Envoyé par cnhkp

Il me semblait bien que «I.capacite» était initialisé à «Instance I» ?

C'est pas totalement faux. Le paramètre Instance I créé une Instance initialisée comme une copie du ce qui est reçu mais l'Instance transmise n'a aucun de ses champs initialisés car provient de Instance I; du main().

Citation:

Envoyé par cnhkp

Quant à l’overflow j’ai cru résoudre le problème cependant j’obtiens une segmentation fault 11 à l’exécution du programme, est-ce lié ?

La boucle allait 1 indice trop loin, elle va maintenant 2 indices trop loin!

Citation:

Envoyé par cnhkp

J’utilise using namespace stp afin de rester dans le cadre du cours qui m’est fourni par la fac qui, je pense, n’est pas à jour sur tout. Bien qu’effectivement c++ 11 ait 7ans.

En fait, ça a été créé pour le portage de code d'avant 1998, donc l'utiliser ici c'est avoir 20 ans de retard!

Citation:

Envoyé par cnhkp

j’ai donc bien remplacé par swap, quant aux références, je ne saisi pas à quelle moment celles-ci doivent intervenir.

Elles sont apparues avant 1989, et sont une des premières choses à connaître pour la passage des paramètres des fonctions avec la bonne utilisation du mot const. Ça n'est pas un "détail", si tes profs l'ont loupé, il faudra rétablir la peine de mort, c'est gravissime.

Sinon, ta classe Instance est curieuse. Elle contient une capacité mais ne peut que stocker qu'un unique Objet, et tu sembles vouloir recréer le concept de std::vector<>!
- Fonction lecture(), tu remplis un tableau local vec qui disparaît (comme toute variable locale) à la sortie de la fonction. Tu souhaitais peut être le mettre sans I.vec qui devrait être un tableau.
- Fonctiontri(), elle ne fonctionne pas. En plus du parcours qui va 2 indices trop loin, la variable inversion est trop souvent mise à 0.
...
24/04/2018, 08h36
Bktero

Citation:

Envoyé par cnhkp

-j’ai donc bien remplacé par swap, quant aux références, je ne saisi pas à quelle moment celles-ci doivent intervenir.

Citation:

Envoyé par dalfab

Elles sont apparues avant 1989, et sont une des premières choses à connaître pour la passage des paramètres des fonctions avec la bonne utilisation du mot const. Ça n'est pas un "détail", si tes profs l'ont loupé, il faudra rétablir la peine de mort, c'est gravissime.

Avant d'acheter planches et poutres pour construire une guillotine, tu peux déjà lire la FAQ ;) https://cpp.developpez.com/faq/cpp/?page=Les-references et https://cpp.developpez.com/faq/cpp/?...-a-ma-fonction
24/04/2018, 13h04
cnhkp

Merci à vous deux pour ces réponses.
Celles-ci s'avèrent effectivement enrichissantes pour moi puisqu'elles m'ouvrent pleins d'axes de recherche et de progression intéressants.
Cependant je suis limité dans le temps et j'ai besoin de réponses plus concrètes sur ma fonction main, en effet j'ai pu tester ma fonction lecture indépendemment et celle-ci donne des résultats qui me sont acceptables, bien que malgré les consignes je n'ai pas (encore) utilisé de références.
En effet, je ne comprends toujours pas concrètement où je dois m'en servir.
De plus savez vous pourquoi mes deux affichages cout ne retourne rien ? J'ai pu corrigé l'erreur de segmentation mais la fonction me renvoie toujours un 0 et rien d'autre.
24/04/2018, 19h31
Invité

Bonsoir,

Et si tu récupérais les sorties de tes fonctions ? ;)

Code:

Instance I = lecture(..);

Code:

auto u_trie = tri(...);

Tel que tu les passes dans ton nouveau code, ce sont des copies que tu manipules au sein de tes fonctions. Tes variables dans le main() restent inchangées.