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