Corrigé Mines-Ponts 2025 Informatique commune MP-PC-PSI — Partie 4 (Q7 à Q11) : Glouton par rapport profit sur ressource, tri par insertion, contre-exemple

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique commune MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Sujet officiel (PDF, site du concours)

Énoncé

Stratégie gloutonne (un choix fait n'est jamais remis en cause) :

on calcule pour chaque objet le rapport $q_{i} = p_{i} / r_{i}$ , rangé dans une liste Lqi, et l'on crée la liste Li des indices, initialement Li[i] $= i$ ;
on trie Lqi par ordre décroissant en déplaçant Li de la même façon, de sorte que Li[j] reste l'indice dans obj de l'objet dont le rapport est en position $j$ ;
partant de la ressource disponible $b$ , on choisit l'objet de plus grand rapport tel que $r_{i} \leq b$ ;
on remplace $b$ par $b - r_{i}$ et l'on recommence en 3 tant qu'un objet peut encore être ajouté.

La fonction construitLi(obj) réalise les étapes 1 et 2 : une première boucle remplit Lqi (ligne 5 à compléter) et Li ; la seconde est un tri par insertion décroissant de Lqi (pour $i$ de $1$ à $n - 1$ : x=Lqi[i], puis tant que j>0 et Lqi[j-1]<x, décalage de Lqi[j-1] en Lqi[j]), où les mises à jour de Li sont à compléter (lignes 12 et 15). Un second programme (lignes 1 à 8) réalise les étapes 3 et 4 : S=len(obj)*[0], Li=construitLi(obj), j=0, une boucle while (ligne 4) contenant un test if …<=b (ligne 5), deux affectations de S et de b (lignes 6, 7), puis j+=1. On admet qu'un tri optimal coûte $Θ (n lo g n)$ dans le pire des cas.

Q7. Pour obj=[(2,3),(1,4),(4,4)] et $b = 5$ , expliquer quelle solution le glouton construit.
Q8. Compléter les lignes 5, 12 et 15 de construitLi.
Q9. Identifier le meilleur et le pire des cas du tri employé, avec leurs complexités justifiées.
Q10. Compléter les lignes 4, 5, 6 et 7 du programme glouton.
Q11. Sur le même exemple, donner la solution optimale ; conclure sur la pertinence du glouton.

Corrigé

Q7. Les rapports profit/ressource valent

$q_{0} = \frac{3}{2} = 1, 5, q_{1} = \frac{4}{1} = 4, q_{2} = \frac{4}{4} = 1,$

d'où l'ordre décroissant : objet $1$ , objet $0$ , objet $2$ (Li $= [1, 0, 2]$ ).

Objet $1$ : $r_{1} = 1 \leq 5$ , on le prend ; il reste $b = 4$ .
Objet $0$ : $r_{0} = 2 \leq 4$ , on le prend ; il reste $b = 2$ .
Objet $2$ : $r_{2} = 4 > 2$ , on ne peut pas le prendre ; plus aucun objet n'est ajoutable.

Le glouton construit $S = [1, 1, 0]$ , de profit $3 + 4 = 7$ pour $3$ ressources consommées sur $5$ .

Q8. Fonction complétée (les lignes ajoutées sont commentées) :


def construitLi(obj):
    Lqi=[]
    Li=[]
    for i in range(len(obj)):
        Lqi.append(obj[i][1] / obj[i][0])   # ligne 5 : q_i = p_i / r_i
        Li.append(i)
    for i in range (1,len(Lqi)):
        x=Lqi[i]
        j=i
        while j>0 and Lqi[j-1]<x:
            Lqi[j]=Lqi[j-1]
            Li[j]=Li[j-1]                   # ligne 12
            j-=1
        Lqi[j]=x
        Li[j]=i                             # ligne 15
    return Li

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →