Discussion :

[malalll]

Bonjour a tous,
le probleme du sac a dos me pose des problemes et je suis incapable de le resoudre alors je demande votre aide et vos remarques
probleme:
Un cambrioleur veut voler n objet
Chaque objet i possède un poids pi et une valeur vi
Son sac peut porter un poids limite Pmax.
Il désire remplir son sac de façon à obtenir une valeur totale la plus grande possible sans dépasser le poids limite du sac.
Le problème peut être décrit par:

Max(∑vi )
∑ pi <=Pmax avec i l’indice de l’objet choisi


voici le code source du programme que j'ai developpéé avec des fichiers input et output .J'ai pas su ou initialiser la variable valeur_optimale

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
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
#include <stdio.h>
int W;
int sac[5],msac[5];
int v[20];
int w[20];
int n;//=5;
int poids_obj,Psac;
int valeur_actuelle,valeur_restante,valeur_potentielle,valeur_optimale ;
int choix(int i,int val,int poi);
 void remplir_l();
  void ecrire();
FILE *fin,*fout;
 
 
 void main()
{ fin=fopen("sac.in","r");
 fout=fopen("sac.out","w");
    remplir_l();
 
for(int i=0;i<n;i++)
{poids_obj=poids_obj+w[i];
 printf("%d ",w[i]); 
 printf("%d \n",v[i]);
sac[i]=msac[i]=0;}
valeur_restante=poids_obj;
valeur_actuelle=Psac=0;
     valeur_optimale=v[0];
choix(0,W,0);
ecrire();
for(int i=0;i<n;i++)
printf("%d",sac[i]);
fclose(fin);
fclose(fout);
int h ;
scanf("%d",h);
}
 
int choix(int i,int w_res,int val_obt)
{
int with,without;
if (i==n)
{
     if (with>without)
     {sac[i]=1 ;return with; }
        else {sac[i]=0;  return without;} }
 if(valeur_actuelle>valeur_optimale)
                     {
                    valeur_optimale=valeur_actuelle;
                    for(int h=0;h<n;h++)
                    {msac[h]=sac[h];
                    printf("%d",msac[h]); }
                    }
                    }
else
 { without = choix( i+1,w_res, val_obt);
     if (w[i]>w_res)  return  val_obt;
     if (w[i]<=w_res)
       {
        with = choix( i+1,w_res-w[i], val_obt+v[i]);
        }
      }
  }
 
 
      /*  valeur_potentielle=valeur_actuelle+valeur_restante;
        printf("\npotentielle=%d\n",valeur_potentielle);
           if( valeur_potentielle-v[i]<valeur_optimale)
             {  printf("\n********entre*******\n");
             sac[i]=1;printf("\nsac[i]=%d\n",sac[i]);
             Psac=Psac+w[i];printf("\nsac= %d\n",Psac);
         valeur_actuelle=valeur_actuelle+v[i]; printf("\nvaleur actuelle=%d\n",valeur_actuelle);
             choix(i+1); valeur_restante=valeur_restante-v[i];
             }
         }
        else
                {sac[i]=0;
             printf("\nsac[i]=%d\n",sac[i]);
             choix(i+1);valeur_restante=valeur_restante-v[i];
             } }        */
 
 
 
 
  void remplir_l()
   {
    int poid,val,nomb,i=0;
    fscanf(fin,"%d ",&W);
   fscanf(fin,"%d ",&nomb);
     n=nomb;
       while(i<n)
        {fscanf(fin,"%d",&poid);
            w[i] = poid;
             fscanf(fin,"%d",&val);
             v[i] =val;
             i++;
        }
   }
 void ecrire()
  {
    fprintf(fout,"valeur_optimale=%d\n",valeur_optimale);
    fprintf(fout," ");
    for (int i=0;i<n;i++)
    if(sac[i]=1)
    fprintf(fout," %d",i);
    fprintf(fout,"\nw ");
    for (int j=0;j<n;j++)
    if(sac[j]=1)
    fprintf(fout,"%d ",w[j]);
    fprintf(fout,"\nv ");
    for (int k=0;k<n;k++)
    if(sac[k]=1)  fprintf(fout,"%d ",v[k]);
     }

si quelqu'un pourrait m'aider je serait reconnaissante
merci d'avance

[davcha]

C'est un problème combinatoire où tu as un certain nombre de contraintes à respecter.

Grosso modo, tu as un ensemble de variables que tu peux modifier, et cet ensemble de variables peut violer des contraintes.
Ici, ton ensembles de variables c'est "quels objets je mets dans le sac ?", et la contrainte violable c'est si la somme du poids des objets est supérieur au poids maximum supportable par le sac.

On cherche à maximiser le nombre d'objets ou le poids maximum ou autre chose... Pour un voleur, je pense qu'il chercherait à maximiser la somme totale de la valeur des objets contenu dans son sac.

Quoiqu'il en soit, les algorithmes génétiques sont vraiment géniaux pour régler les problèmes combinatoires de ce genre.

Si tu as des questions après avoir lu ça, n'hésite pas.

[notalp]

regarde aussi les algo d'optimisation. (Lagrangien ... )

[ToTo13]

Bonjour,

il me semble que le problème est appartient à la classe P.
Il ne sera donc pas facile à résoudre avec des méthodes directes et exaustives.

- Cherche du cotés des méta heuristique comme la méthode Tabou principalement.
- Il y a de nombreux algo issuent de l'IA qui traite ce genre de problèmes.

[Jedai]

Bonjour,

il me semble que le problème est appartient à la classe P.
Il ne sera donc pas facile à résoudre avec des méthodes directes et exaustives.

Tu voulais dire qu'il appartient à la classe des problèmes NP complets plutôt parce que la classe P (Polynomiale) ne présente guère de difficulté...

--
Jedaï

[ToTo13]

Bonjour,

oups effectivement...