Comment définir le cas de base pour un rendu de monnaie avec programmation dynamique ?

Réponse courte

Pour le minimum de pièces, pose M(0) = 0 : rendre zéro ne demande aucune pièce. Initialise les autres sommes comme impossibles, puis remplace leur valeur quand une pièce mène à un reste déjà réalisable.

Comprendre

La somme nulle est la base

On note M(s) le nombre minimal de pièces pour rendre exactement la somme s. Si s vaut zéro, aucune pièce n’est nécessaire : M(0) = 0. Cette valeur permet de calculer les petites sommes, puis les plus grandes. Les pièces doivent être strictement positives et leur stock illimité dans cette modélisation.

Ne pas confondre impossible et zéro

Pour remplir une table jusqu’à une cible S, crée S + 1 cases. Mets 0 à l’indice 0 et une valeur spéciale d’impossibilité dans les autres cases au départ. Pour chaque somme s croissante et chaque pièce c ≤ s, si M(s − c) est réalisable, compare 1 + M(s − c) aux candidats déjà trouvés. Le minimum conservé devient M(s).

Exemple avec les pièces 2 et 5

Au départ, M(0) vaut 0 ; les sommes 1 et 3 restent impossibles, et M(2) devient 1 grâce à la pièce 2. La valeur spéciale ne doit pas être prise pour zéro : sinon une somme impossible pourrait sembler atteinte sans pièce. Si la table de la somme cible reste impossible, il faut annoncer qu’aucune combinaison n’existe. Avec un stock limité, la somme seule ne suffit plus à définir l’état.

Étapes

  1. Définis M(s) comme le nombre minimal de pièces pour rendre exactement s.
  2. Crée les cases de 0 à la cible, pose M(0) = 0 et initialise les autres comme impossibles.
  3. Parcours les sommes positives dans l’ordre croissant ; pour chaque pièce qui ne dépasse pas s, considère 1 + M(s − c) seulement si ce reste est réalisable.
  4. Lis la case de la cible : une valeur impossible signifie qu’aucune combinaison de pièces ne convient.

Exemples

  • Avec les pièces 2 et 5, M(0) = 0 : il ne faut rien ajouter pour rendre zéro.
  • Avec 2 et 5, M(1) reste impossible, tandis que M(2) = 1 grâce à une pièce de valeur 2.
  • Avec les pièces 1, 3 et 4, M(6) = 2, car 3 + 3 rend exactement 6 en deux pièces.

Pièges fréquents

  • Initialiser toutes les cases à zéro fait croire qu’une somme impossible peut être rendue sans pièce et fausse les minimums calculés ensuite.
  • Oublier d’ajouter 1 à M(s − c) ne compte pas la dernière pièce choisie et sous-estime le nombre total de pièces.

Pourquoi ça marche

Chaque solution d’une somme positive se construit en ajoutant une pièce à une solution du reste ; M(0) fournit l’arrêt naturel de cette décomposition.

Et maintenant ?

Questions proches

← Toutes les questions-réponses