Corrigé Mines-Ponts 2025 Informatique commune MP-PC-PSI — Parties 2 et 3 (Q3 à Q6) : Profit, contrainte et arbre binaire des solutions

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é

Objets. Tout le reste du sujet est en Python. Les objets sont codés par une liste obj de longueur $n$ : obj[i] est le tuple (ri, pi) des valeurs $r_{i}$ (ressource consommée) et $p_{i}$ (profit). Une solution est une liste S $= [x_{0}, \dots, x_{n - 1}]$ de $0$ et de $1$ . La fonction sum est interdite dans Q3 et Q4.

Q3. Écrire profit(obj, S) qui renvoie le profit $P$ de la solution.
Q4. Écrire contrainte(obj, S, b) qui renvoie True si la contrainte de ressources est respectée, False sinon.

Arbre des solutions. Sans tenir compte de la contrainte, on représente toutes les solutions par un arbre binaire : la racine décide de l'objet $0$ , le niveau suivant de l'objet $1$ , etc. ; le fils gauche correspond à $x_{i} = 1$ (objet choisi), le fils droit à $x_{i} = 0$ . Chaque feuille porte la solution lue le long du chemin depuis la racine.

Figure 1 — Arbre binaire et espace des solutions pour $n = 3$ (le nombre d'un nœud est l'indice de l'objet sur lequel il décide).

Q5. Pour $n = 3$ , donner la solution S associée aux feuilles b et c.
Q6. Donner le nombre de feuilles en fonction de $n$ ; en déduire, en la justifiant, la complexité d'une résolution par force brute qui essaie toutes les sélections d'objets.

Corrigé

Q3. On accumule $p_{i} x_{i}$ dans un accumulateur initialisé à $0$ , l'indice $i$ parcourant à la fois obj et S (les deux listes ont la longueur $n$ ). Le profit de l'objet $i$ est la seconde composante du tuple, obj[i][1].


def profit(obj: [(int)], S: [int]) -> int:
    P = 0
    for i in range(len(obj)):
        P = P + obj[i][1] * S[i]
    return P

Multiplier par $x_{i} \in {0, 1}$ évite un test : le terme vaut $p_{i}$ si l'objet est choisi, $0$ sinon. Coût : une boucle de $n$ tours à corps en $O (1)$ , donc $O (n)$ .

Q4. Même accumulation sur les ressources (première composante obj[i][0]), puis comparaison à $b$ .


def contrainte(obj: [(int)], S: [int], b: int) -> bool:
    R = 0
    for i in range(len(obj)):
        R = R + obj[i][0] * S[i]
    return R <= b

Ce que le correcteur attend : renvoyer directement le booléen R <= b, plutôt que if R <= b: return True else: return False (remarque explicite du jury). Coût $O (n)$ .

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 →