La solution de l’exercice S. 2.
Pour une
solution simple, il est conseillé d’utiliser la programmation dynamique. De
quoi s’agit-il ? Nous allons d’abord présenter cette méthode à travers un
exemple concret..
Exercice : Calculer
le n ème nombre de Fibonacci.
Première
solution :
#include <stdio.h> #include <sys/types.h> int n; long int fib(int n1) { if (n1 < 2) return(n1); return(fib(n1-1)+fib(n1-2)); } main() { scanf("%d",&n); printf("F(%d)=%d\n",n,fib(n));} |
C’est le
programme récursif correspondant à la définition des nombres de Fibonacci. En le testant, nous avons des surprises déjà
dans le cas de n=45 . Si l’on calcule le nombre d’instruction
nécessaires, on obtient au moins F(n)
pas pour calculer F(n) , ce qui est supérieur à an-2
(où a~=1.618), donc un grand nombre exponentiel. Déjà pour calculer F(45,
le programme met 42 secondes et
exécute plus de F(45)=1134903170
instructions. D’où vient cette lenteur ? En examinant le
déroulement du programme, on se rend compte qu’il calcule certaines données de
nombreuses fois (par exemple la valeur de F(2) ).
La méthode qui
permet d’éviter ce surplus de travail s’appelle la programmation dynamique.
L’idée est que si l’on a déjà calculé une donnée, on la note et au lieu de
recalculer chaque fois que l’on en a besoin, on la cherche dans nos notes. Les
résultats partiels doivent être calculés dans le bon ordre, du plus petit au
plus grand pour que les données nécessaires à un calcul soient déjà disponibles.
Qu’est-ce que
cela signifie pour l’exemple ci-dessus ? Que nous avons intérêt de calculer
pour chaqu i la valeur de F(i) , comme par exemple dans le
programme ci-dessous :
#include <stdio.h> #include <sys/types.h> long int F[50], n, i; main() { scanf("%d",&n); F[0]=0; F[1]=1; for (i=2; i<=n; i++) F[i]=F[i-1]+F[i-2]; printf("F(%d)=%d\n",n,F[n]);} |
Ce
programme met 0,01 seconde pour calculer la valeur de F(45), et exécute
pour cela n+1 instructions.
La solution de l’exercice du sac à dos avec la
méthode de programmation dynamique
Nous devons d’abord définir les
calculs partiels. Nous calculons pour chaque 0≤i<n-re et chaque
j≤w la valeur maximale pouvant être chargée, en utilisant les i+1
premiers objets, dans le sac à dos de capacité
j. (les objets sont numérotés de 0 à n-1.) Ceci est chargé dans une pile T
, donc pour une valeur de i donné, T [ j ] désigne la valeur pouvant être chargée, en utilisant les i+1
premiers objets, dans le sac à dos de capacité
j. Mais si l’on utilise la même pile T pour chaque i, on doit faire attention à calculer les nouvelles valeurs T[j]
dans le bon ordre.
Nous pouvons
remarquer que pour calculer une nouvelle valeur T[j] , deux cas se
présentent :
- En
utilisant les premiers i+1 objets, on peut charger dans le sac de
capacité j la même valeur qu’en utilisant les i premiers objets,
alors la valeur de T[j] ne change pas, ou bien
- Nous
pouvons charger un valeur plus grande et donc on doit utiliser le i ème
objet , et ainsi T[j]=E[i]+T[j-V[i]], si T[j-V[i]] contient
la valeur maximale pouvant être chargée en utilisant les i premiers
objets. (Ici E[i] désigne la valeur du i ème objet, V[i]
sa masse. On utilise le principe de la suboptimalité qui dit en grandes lignes
que dans une solution optimale une solution partielle donne nécessairement
la solution optimale du problème partiel correspondant. Si ceci n’est pas
valable dans un certain cas, alors nous n’avons aucune chance de trouver
avec la programmation dynamique la solution optimale.)
Le code correspondant :
for (i=0; i<=w; i++) T[i] = 0; for (i=0; i<n; i++) { for (j=w; j>=V[i]; j--) { if (T[j-V[i]]+E[i] > T[j]) { T[j] = T[j-V[i]]+E[i]; } } } printf("Valeur maximale : %d\n", T[w]); |
Ceux qui ont donné cette méthode,
ont déjà obtenu 9 points. Ce programme
fonctionne bien seulement si la valeur de w est petite. Si w est
grand mais la valeur possible des trésors est petite, on peut alors écrire un
autre programme dynamique seblable. totvaleur désigne la somme des
valeurs des objets (si on connaît une meilleure estimation pour majorer la
valeur optimale, on peut aussi l’écrire dans cette variable). Dans la i ème itération T[j] contient
la masse minimale pour charger exactement la valeur j en utilisant les
premiers i+1 objets. Si on ne
peut pas le faire du tout, alors on charge la valeur w+1 ( au lieu de
l’infini ). Ici, il est vrai aussi que, en calculant T[j] , si la
solution optimale ne contient pas le i ème objet, alors la valeur T[j]
ne change pas ; si elle le contient, alors T[j]=T[j-E[i]]+V[i]. Le
code correspondant :
for (i=1; i<=totvaleur; i++) T[i] = w+1; T[0] = 0; for (i=0; i<n; i++) { for (j=totvaleur; j>=E[i]; j--) { if ((T[j-E[i]]+V[i] < T[j])) { T[j] = T[j-E[i]]+V[i]; } } } for (i=totvaleur; i>=0; i--) { if (T[i] <= w) { max = i; i = 0; } } printf("Valeur maximale : %d\n", max); |
Parmi les deux
solutions il faut choisir celle qui serait plus rapide dans un cas précis. Vous
pouvez télécharger le programme complet en C
ici .
#include <stdio.h>
main()
{ int *E, *V, *T;
int n, w, v1, e1, i, j, max;
int akt_n = 0;
int totvaleur = 0;
scanf("%d%d",&n,&w);
if ((E = (int *) malloc(n*sizeof(int))) == NULL) { printf("Allocation error\n"); exit(2);
}
if ((V = (int *) malloc(n*sizeof(int))) == NULL) { printf("Allocation error\n"); exit(2);
}
for (i=0; i<n; i++) { scanf("%d%d",&v1,&e1); if (v1 <= w) { V[akt_n] = v1;
E[akt_n] = e1;
totvaleur += e1;
akt_n++;
}
}
n = akt_n;
if (w <= totvaleur) { if ((T = (int *) malloc((w+1)*sizeof(int))) == NULL) { printf("Allocation error\n"); exit(2);
}
for (i=0; i<=w; i++) T[i] = 0;
for (i=0; i<n; i++) { for (j=w; j>=V[i]; j--) { if (T[j-V[i]]+E[i] > T[j]) { T[j] = T[j-V[i]]+E[i];
}
}
}
printf("Valeur maximale : %d\n", T[w]);
} else { if ((T = (int *) malloc((totvaleur+1)*sizeof(int))) == NULL) { printf("Allocation error\n"); exit(2);
}
for (i=1; i<=totvaleur; i++) T[i] = w+1;
T[0] = 0;
for (i=0; i<n; i++) { for (j=totvaleur; j>=E[i]; j--) { if ((T[j-E[i]]+V[i] < T[j])) { T[j] = T[j-E[i]]+V[i];
}
}
}
for (i=totvaleur; i>=0; i--) { if (T[i] <= w) { max = i;
i = 0;
}
}
printf("Valeur maximale : %d\n", max); } }
