Une histoire de monnaie
Cette feuille en Postscript

1  Approche gloutonne

Un système monétaire est une suite (finie) strictement décroissante (di) d'entiers (naturels non-nuls). Chaque di est une espèce. Par exemple, le système de l'Euro est ⟨ 500, 200, 100, 50, 20, 10, 5, 2, 1 ⟩ et l'ancien système britannique est ⟨ 240, 60, 30, 24, 12, 6, 3, 1 ⟩. On s'intéresse au problème du paiement exact d'un montant quelconque dans un système donné.
  1. Une première question est celle de la possibilité de payer. Trouver une condition nécessaire et suffisante pour qu'un système monétaire permette de payer n'importe quel montant.

  2. Une seconde question est de payer avec le minimum d'espèces (paiement optimal).

    Décrire une approche gloutonne du paiement optimal.

  3. Programmer l'approche gloutonne.
    static int [] glouton(int [] d, int m) ;
    Pour un système monétaire ⟨ d0, d1, … dk-1 ⟩ et un montant m, La méthode (statique) glouton renvoie un tableau d'entiers t tel que.
    k-1
    i=0
    ti × di = m
    Attention, on se contraindra à atteindre une complexité en O(k).

    Au passage et plus précisément, les paiements sont représentés par des tableaux t de taille k. Le cardinal d'un paiement est tout bêtement le nombre d'espèces concrètes dans un paiement, c'est-à-dire la somme des ti. Un paiement de m est optimal quand son cardinal est minimal parmi ceux des paiements de m.

  4. On va montrer que la stratégie gloutonne est optimale dans le cas du système européen.

    Soit un paiement donné T = ⟨ t0, t1, …, tk-1 ⟩, on note Vi(T) le montant obtenu en annulant tous les tj de 0 à i-1.
    V i(T) =
    k-1
    j=i
    tj × dj
    (On constate que si T est un paiement optimal, Ti obtenu en annulant tous les tj de 0 à i-1 est également un paiement optimal.)
    1. Montrer que, dans système européen et pour tout paiement T optimal on a :
      Vi(T) < di-1
      Le plus simple me semble de compléter le tableau suivant, qui donne pour chaque entier i entre 9 et 2, le plus grand Vi(T) possible (noté bi).
      i 8 7 6 5 4 3 2 1
      di-1 2 5 10 20 50 100 200 500
      bi 1 4          
      La borne b8 s'explique en considérant que T optimal ne peut pas contenir plus d'une pièce d'un euro (car on peut remplacer deux pièces d'un euro par une pièce de deux euros). La borne b7 s'explique de façon à peine plus complexe, T optimale ne peut pas contenir 3 pièces de deux euros ou plus (par le remplacement 2 + 2 + 2 → 5 + 1), et deux pièces de deux euros ne peuvent être accompagnées d'une pièce d'un euro (car 1 + 2 + 2 = 5).

    2. Monter que la condition ci-dessus entraîne l'optimalité de la stratégie gloutonne.


  5. Montrer que la stratégie gloutonne n'est pas optimale dans le cas du système britannique.
Solution.

2  Recherche exhaustive

À cause de l'existence du système britannique, le paiement optimal ne peut pas reposer sur l'algorithme glouton. On cherche une solution générale.
  1. Décrire une technique inductive pour engendrer l'ensemble des paiements d'une somme donnée m dans un système donné (di).

  2. Écrire une méthode tous, qui affiche tous les paiements possibles.
    static void tous(int [] d, int m)

    On suppose donnée une méthode d'affichage dump que voici :
      static void dump(PrintStream out, int [] system, int [] t) {
        
    for (int i = 0 ; i < t.length ; i++) {
          
    int d = system[i] ;
          
    for (int j = 0 ; j < t[i] ; j++)
            out.print(" " + d) ;
        }
        out.println() ;
      }

    Dans ce type de programmes (comme par exemple dans le devoir maison numéro deux, ou le contrôle hors-classement) on essaie d'éviter d'allouer trop. Représentons un paiement par le tableau des ti (un tableau t) de taille k (nombre d'espèces du système).

    Il s'agit en gros de fabriquer tous les t possible. Une solution économique en espace utilisera une méthode zyva.
    static void zyva(int [] d, int m, int i, int [] t)
    Dans un appel à zyva, le tableau t n'est « rempli » que de 1 à i-1 et m est un prix à atteindre en utilisant seulement les espèces d'indice supérieur ou égal à i. Les arguments t, i, et m sont liés :
    m +
    i-1
    j=0
    tj × dj = m0
    (Où m0 est le prix initial.)

    Ainsi tous s'écrit très simplement :
      static void tous(int [] d, int m) {
        zyva(d, m, 0, 
    new int[d.length]) ;
      }


  3. Transformer tous en exhaustif, qui renvoie une somme optimale.
    static int [] exhaustif(int [] d, int m)


  4. Il n'est pas besoin de parcourir tous les paiements possibles pour trouver un paiement optimal. En effet supposons connu un paiement de cardinal c0. Pour un appel donné de zyva, on dispose d'un paiement partiel ⟨ t0, t1, …, ti-1 ⟩ de cardinal c, et il reste à payer m à l'aide des espèces ⟨ di, di+1, …, dk-1 ⟩. On ne peut certainement pas compléter t en un paiement optimal dans les deux cas suivants : On peut alors élaguer la recherche, c'est-à-dire renoncer à compléter le paiement partiel t. Modifier la recherche exhaustive pour profiter de ces remarques.
Solution.

3  Paiement dynamique

La programmation dynamique revient à échanger du temps contre de l'espace. Sans plus tergiverser voici une solution au problème du paiement optimal qui emploie cette technique.
   1   static int [] dynamiqueCard(int [] d, int m) {
   2     
int k = d.length ;
   3     
int [] card = new int [m+1] ;
   4 
   5     card[0] = 0 ; 
// Inutile en Java
   6     
for (int n = 1 ; n <= m ; n++) {
   7       
int r = m+1 ;
   8       
int i ;
   9       
for (i = 0 ; d[i] > n ; i++)
  10         ;
  11       
for (; i < k ; i++) {
  12         
int di = d[i] ;
  13         
if (card[n-di]+1 < r) {
  14           r = card[n-di]+1 ;
  15         }
  16       }
  17       card[n] = r ;
  18     }
  19     
return card ;
  20   }
La méthode dynamiqueCard renvoie un tableau d'entiers c[0…m], tel que c[n] est le cardinal d'un paiement optimal de n.
  1. Expliquer le commentaire de la ligne 5.

  2. Comment comprendre la boucle des lignes 9-10 ? Pourquoi termine-t-elle toujours ?

  3. Montrer que tous les accès dans les tableaux sont légaux.

  4. Donner le coût de la méthode dynamiqueCard.

  5. Argumenter la correction de la méthode dynamiqueCard. On se contentera d'une définition inductive de M(n), cardinal d'un paiement optimal de n.

  6. Comment faire pour trouver un paiement optimal de m et non plus seulement son cardinal ?
Solution.

Note

Toutes les solutions sont regroupées dans la classe Monnaie, également disponible sous forme imprimable.


Ce document a été traduit de LATEX par HEVEA et HACHA.