DS 7 — Sac à dos fractionnaire¶
MP2I, année scolaire 2022-2023. Durée totale 4h.
Tout document interdit. Tout dispositif électronique interdit.
On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles.
Chaque problème est à traiter sur une copie séparée pour ne pas avoir de confusion entre les numérotations.
Sac à dos fractionnaire¶
On considère le problème suivant :
Problème : SacADosFractionnaire
Entrées :
- \(n\) objets numérotés de \(1\) à \(n\).
- à chaque objet on associe deux entiers :
- \(w_i\) son poids
- \(v_i\) sa valeur
- Un poids maximal \(W \in \N\)
Pour \(\sigma : \range{1}{n} \rightarrow \Q_+ \cap [0;1]\), on note \(w(\sigma) = \sum_{x = 1}^{n} w_x \sigma(x)\), le poids de \(\sigma\), et \(v(\sigma) = \sum_{x = 1}^{n} v_x \sigma(x)\) sa valeur.
On cherche
C'est-à-dire que l'on cherche la répartition d'objets maximisant la valeur en restant dans la limite de poids.
Chacun des \(\sigma(x)\) représente la proportion de l'objet \(x\) que l'on rajoute dans le sac. Pour que cette proportion soit représentable informatiquement, on se restreint à des rationnels, mais dans la suite, on considérera des flottants sans se poser de questions.
Pour résoudre ce problème, on se propose d'effectuer un algorithme glouton : on identifie l'objet qui représente le choix glouton et on place le maximum de cet objet dans le sac, c'est-à-dire soit l'objet en entier s'il rentre, soit la proportion suffisante pour saturer le sac.
Q.1 Rappeler brièvement le principe d'un algorithme glouton et du choix glouton.
Implémentation et tri¶
On va implémenter ce problème en C en représentant un problème par un
élément du type :
struct sacados {
int nobjets;
int *poids;
int *valeurs;
int poids_maximal;
};
typedef struct sacados sacados;
On suppose ainsi que toutes les valeurs sont entières. Les tableaux représentant les poids et les valeurs doivent donc être alloués en plus de la structure.
Attention : afin de simplifier l'implémentation les objets sont numérotés de 0 à n-1 dans les questions de code uniquement.
Q.2 Écrire des fonctions de prototype :
sacados *sacados_alloue(int n);
void sacados_libere(sacados *sac);
qui vont respectivement allouer une instance du sac à dos pour n objets et libérer un sac à dos précédemment alloué.
Les deux fonctions utilisées successivement ne doivent pas produire de fuite de mémoire.
Corrigé
sacados *sacados_alloue(int n)
{
sacados *s = malloc(sizeof(sacados));
s->nobjets = n;
s->poids = malloc(sizeof(int) * n);
s->valeurs = malloc(sizeof(int) * n);
return s;
}
void sacados_libere(sacados *sac)
{
free(sac->poids);
free(sac->valeurs);
free(sac);
}
On va étudier différents critères pour trier les objets afin d'élaborer un algorithme glouton. Comme on ne peut pas passer des fonctions en argument, dans les limites du programme, on ne peut pas faire en sorte facilement de trier selon différents paramètres. On va considérer ici qu'on a défini une fonction
bool sacados_cmp(sacados *sac, int i, int j);
qui compare selon le critère retenu les deux objets d'indices \(i\) et \(j\) et renvoie un booléen indiquant si \(i\) est plus petit strictement que \(j\).
Q.3 Écrire une fonction de prototype
int *tri_objets(sacados *sac);
qui renvoie un tableau de \(n\) éléments t où
t[i] est l'indice du \(i\)ème objet dans l'ordre croissant induit
par la fonction de comparaison.
Note : on pourra implémenter le tri que l'on souhaite ici. Notamment, un tri de complexité non optimale sera accepté.
Corrigé
On trie par insertion le tableau des indices \(0, \dots, n-1\).
void echange(int *t, int i, int j)
{
int temp = t[i];
t[i] = t[j];
t[j] = temp;
}
int *tri_objets(sacados *sac)
{
int n = sac->nobjets;
int *t = malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
t[i] = i;
}
// tri par insertion
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && sacados_cmp(sac, t[j], t[j-1]); j--) {
echange(t, j, j-1);
}
}
return t;
}
Q.4 En déduire une fonction de prototype
float *sacados_resout(sacados *sac);
qui alloue et renvoie une solution gloutonne au sac à dos fractionnaire.
Le ième élément du tableau sera la proportion du ième objet.
Indication : les valeurs dans ce tableau sont toutes des 0 ou des 1, sauf au plus une valeur dans \(]0;1[\).
Corrigé
float *sacados_resout(sacados *sac)
{
float *p = malloc(sizeof(float) * sac->nobjets);
for (int i = 0; i < sac->nobjets; i++) {
p[i] = 0.;
}
int *t = tri_objets(sac);
float reserve = sac->poids_maximal;
for (int i = 0; i < sac->nobjets; i++)
{
int k = t[i];
if (sac->poids[k] > reserve) {
p[k] = reserve / sac->poids[k];
break;
}
p[k] = 1.0;
reserve -= sac->poids[k];
}
free(t);
return p;
}
Des mauvais choix gloutons¶
Privilégier les grandes valeurs¶
Dans ce paragraphe, on considère que le choix glouton est l'objet de plus grande valeur.
Q.5 Écrire le corps de la fonction sacados_cmp avec cette approche.
Attention, à ce qu'on a supposé quand on a défini tri_objets.
Corrigé
Comme tri_objets trie dans l'ordre croissant et que sacados_resout
prend les objets dans cet ordre, l'objet « le plus petit » doit être celui
de plus grande valeur.
bool sacados_cmp(sacados *sac, int i, int j)
{
return sac->valeurs[i] > sac->valeurs[j];
}
Q.6 Dérouler l'algorithme glouton qu'on peut en déduire sur l'exemple suivant :
- \(n = 4\) et \(W = 50\)
- \(w_1 = 10\) et \(v_1 = 60\)
- \(w_2 = 10\) et \(v_2 = 60\)
- \(w_3 = 20\) et \(v_3 = 100\)
- \(w_4 = 30\) et \(v_4 = 120\)
Q.7 Que peut-on déduire de l'exemple précédent ?
Privilégier les petits poids¶
Dans ce paragraphe, on considère que le choix glouton est l'objet de plus petit poids.
Q.8 Écrire le corps de la fonction sacados_cmp avec cette approche.
Corrigé
bool sacados_cmp(sacados *sac, int i, int j)
{
return sac->poids[i] < sac->poids[j];
}
Q.9 Dérouler l'algorithme glouton qu'on peut en déduire sur l'exemple du paragraphe précédent.
Q.10 Montrer que ce n'est quand même pas un algorithme optimal.
Efficacité relative¶
Pour chaque objet, on calcule son efficacité \(e_i = v_i / w_i\). On trie alors les objets par efficacité décroissante et on sélectionne tous les objets tant qu'on reste sous le poids, le premier objet qui force un dépassement est placé de manière fractionnelle.
Q.11 Écrire le corps de la fonction sacados_cmp avec cette approche.
Corrigé
L'objet \(i\) est « plus petit » que \(j\) quand il est plus efficace : \(\frac{v_i}{w_i} > \frac{v_j}{w_j}\), ce qu'on teste sans division (les poids sont strictement positifs).
bool sacados_cmp(sacados *sac, int i, int j)
{
return sac->valeurs[i] * sac->poids[j] > sac->valeurs[j] * sac->poids[i];
}
On va se placer dans le cas où \(\sum_{i=1}^n w_i > W\), sinon la solution triviale consistant à prendre tous les objets fonctionne.
Q.12 En déduire que si \(\tau\) est une solution optimale, alors \(w(\tau) = W\).
On suppose qu'on a obtenu une solution gloutonne donnée par \(\sigma\) et qu'on dispose également d'une solution optimale \(\tau\). Pour simplifier, on peut supposer les objets rangés par efficacité décroissante, ainsi \(1\) est l'objet d'efficacité maximale.
Q.13 Montrer que si \(\sigma(1) > \tau(1)\), alors on peut en déduire une solution optimale \(\tau'\) telle que \(\tau'(1) = \sigma(1)\).
Q.14 Justifier que si \(\tau\) est optimale pour les objets de \(1\) à \(n\), alors \(\tau^*\) la restriction de \(\tau\) à \(\range{2}{n}\) est également optimale pour cette instance avec \(W - \tau(1) w_1\) comme poids limite.
Q.15 Justifier que \(\sigma^*\), la restriction de \(\sigma\) à \(\range{2}{n}\), est également donnée par l'algorithme glouton pour le poids limite \(W-\sigma(1) w_1\).
Q.16 En déduire, par récurrence sur le nombre d'objets, que le glouton renvoie une solution optimale.