Le glouton fractionnaire qui a raison

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 7 — Algorithmes gloutons

Énoncé

Soit un sac à dos de capacité $10$ kg et des denrées fractionnables : $(6 kg, 30)$ , $(5 kg, 20)$ , $(4 kg, 24)$ , où chaque couple représente le poids et la valeur totale disponible. Définir le critère glouton et la valeur maximale obtenue.

Corrigé

Puisque les denrées sont fractionnables, le critère optimal est le tri par densité de valeur (valeur/poids) :

Denrée 1 : $30/6 = 5$ /kg
Denrée 2 : $20/5 = 4$ /kg
Denrée 3 : $24/4 = 6$ /kg. L'algorithme trie les denrées par densité décroissante : Denrée 3, puis Denrée 1, puis Denrée 2.
Prendre la totalité de la Denrée 3 ( $4$ kg, valeur $= 24$ ). Reste $6$ kg.
Prendre la totalité de la Denrée 1 ( $6$ kg, valeur $= 30$ ). Reste $0$ kg. Le sac est rempli avec une valeur totale maximale de $24 + 30 = 54$ . Un critère "plus grande valeur d'abord" conduirait à choisir l'objet 1 ( $6$ kg, valeur $30$ ) puis $4$ kg de l'objet 2 ( $4 \times 4 = 16$ ), soit $46$ , ce qui est sous-optimal.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.