algorithmique (école d'ingénieur) · Chapitre 2 · Exercice de TD

Choisir ses projets

Le sac de valeur maximum · niveau 1 (application)

Énoncé

Une association dispose d'un budget de $10$ k€. Cinq projets lui sont proposés ; le projet $i$ coûte $c_{i}$ k€ et rapporte un bénéfice social estimé à $b_{i}$ points :

projet $i$	0	1	2	3	4
coût $c_{i}$	4	3	5	2	6
bénéfice $b_{i}$	7	5	9	3	10

Reconnaître un problème du cours : quels sont les objets, leurs tailles, leurs valeurs, la contenance ?
Calculer le bénéfice maximum et les projets retenus. Comparer avec les deux gloutons.

Corrigé

C'est le sac de valeur maximum : les objets sont les projets, la taille d'un objet est le coût $c_{i}$ , sa valeur est le bénéfice $b_{i}$ , la contenance est le budget $C = 10$ .
Le programme du cours donne un bénéfice maximum de $17$ , avec les projets $1$ , $2$ , $3$ (coût $3 + 5 + 2 = 10$ , bénéfice $5 + 9 + 3 = 17$ ). Le glouton par bénéfices décroissants prend les projets $4$ ( $10$ points, $6$ k€) et $0$ ( $7$ points, $4$ k€) : $17$ aussi. Le glouton par rapport bénéfice/coût prend le projet $2$ (rapport $1, 8$ ) puis le projet $0$ ( $1, 75$ ) ; il reste $1$ k€, rien n'entre : $16$ . Deux solutions optimales différentes existent ici ; le glouton par bénéfices en trouve une par chance.

100 % gratuit

La suite du chapitre est sur Adloun

Exercice suivant et tuteur

Sans compte : le cours, le premier QCM et 2 minutes de podcast et de vidéo. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant et tuteur →