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