Rendu de Monnaie (DP)

Programmation dynamique — quand le glouton échoue

Exercice Intermédiaire · Algorithmique · prepa scientifique et economique (CPGE)

Enonce

Écrire rendu_monnaie(pieces, montant) qui renvoie le nombre minimum de pièces pour atteindre exactement montant (on peut réutiliser chaque pièce autant de fois que nécessaire). Retourne -1 si c'est impossible.

Exemple : rendu_monnaie([1, 3, 4], 6) == 2 (avec deux pièces de 3).

⚠ Contrainte : utilise la programmation dynamique. Observe bien que le glouton échoue sur certains systèmes de pièces.

Signature attendue

def rendu_monnaie(pieces: list, montant: int) -> int:

Exemples

rendu_monnaie([1, 3, 4], 6) → 2 (3 + 3, glouton donnerait 3)
rendu_monnaie([1, 2, 5], 11) → 3 (5 + 5 + 1)
rendu_monnaie([2], 3) → -1 (impossible)

📖 Rappel de cours

On reprend le problème du rendu de monnaie (cf. exercice 13) mais cette fois avec un système de pièces quelconque. Le glouton ne donne plus toujours la solution optimale.

Contre-exemple célèbre :

Avec les pièces [1, 3, 4] et un montant de 6 :

Glouton : 4 + 1 + 1 = 3 pièces
Optimal : 3 + 3 = 2 pièces

Récurrence (DP bottom-up) :

Soit $N(k)$ le nombre minimal de pièces pour rendre la somme $k$.

$N(0) = 0$
$N(k) = 1 + \min_{p \in P,\ p \leq k} N(k - p)$

Complexité $O(M \cdot |P|)$ où $M$ est le montant et $|P|$ le nombre de pièces.

← Exercices d'algorithmique en Python — tris, dichotomie, récursivité

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.