1. Les notations sont assez lourdes alors autant décrire.

  2. Comme souvent dans ce genre de programmes, il faut tenter d'utiliser le moins de mémoire possible, l'idée est ici de construire un paiement progressivement de la gauche vers la droite, dans un tableau passé en argument.
      private static void zyva (int d[], int m, int i, int [] r) {
        
    if (d[i] == 1) {
          r[i] = m ;
          dump(
    System.out, d, r) ;
        } 
    else {
          
    int di = d[i] ;
          
    int max = m/d[i] ;
          
    for (int j = 0 ; j <= max ; j++) {
            r[i] = j ;
            zyva(d, m-j*di, i+1, r) ;
          }
        }
      }

      
    static void tous(int [] system, int m) {
        zyva(system, m, 0, 
    new int[system.length]) ;
      }
  3. On peut à la place de l'impression (dump), comparer le paiement engendré r à un paiement minimal courant. Le paiement minimal courant est idéalement rangé dans une variable statique. Il semble assez logique de calculer le cardinal des paiements en même temps que les paiements eux-mêmes. Il vient :
      private static int minCard ;
      
    private static int [] minR  ;

      
    private static void check(int card, int [] r) {
        
    if (card < minCard) {
          minCard = card ;
          
    for (int i = 0 ; i < r.length ; i++)
            minR[i] = r[i] ;
        }
      }

      
    private static void look(int [] d, int m, int i, int card, int [] r) {
        
    int di = d[i] ;
        
    if (di == 1) {
          r[i] = m ;
          check(card + m, r) ;
        } 
    else {
          
    int max = m/di ;
          
    for (int j = 0 ; j <= max ; j++) {
            r[i] = j ;
           look(d, m-j*di, i+1, card+j,r) ;
          }
        }
      }

      
    static int [] exhaustif(int [] system, int m) {
        
    int len = system.length ;
        minR = 
    new int [len] ;
        minCard = Integer.MAX_VALUE ;
        look(system, m, 0, 0, 
    new int [len]) ;
        
    return minR ;
      }
    Noter que l'on peut remplacer la ligne :
           look(d, m-j*di, i+1, card+j,r) ;
    par :
           look(d, m, i+1, card+j,r) ;
           m -= di ; 
    // Pour m = m - di
    On fait ainsi disparaître des multiplications (coûteuses en temps calcul), mais c'est du chipotage.

    Le coût exact n'est pas facile à évaluer, mais une rapide étude expérimentale montre qu'il y a problème (payer une forte somme dans le système européen par exemple).

  4. En s'inspirant des remarques de l'énoncé, on transforme simplement look ainsi :
     private static void lookOpt(int [] d, int m, int i, int card, int [] r) {
        
    int di = d[i] ;
        
    if (card < minCard && di*(minCard-card) >= m) {
          
    if (di == 1) {
            r[i] = m ;
            check(card + m, r) ;
          } 
    else {
            
    int max = m/di ;
            
    for (int j = max ; j >= 0 ; j--) {
              r[i] = j ;
              lookOpt(d, m-j*di, i+1, card+j,r) ;
            }
          }
        }
      }

      
    static int [] exhaustifOpt(int [] system, int m) {
        
    int len = system.length ;
        minR = glouton(system, m) ;
        minCard = card(minR) ;
        lookOpt(system, m, 0, 0, 
    new int [len]) ;
        
    return minR ;
      }

      
    static int card(int [] t) {
        
    int r = 0 ;
        
    for (int i = 0 ; i < t.length ; i++)
          r += t[i] ;
        
    return r ;
      }
    On remarque que minR et minCard sont initialisées avec la solution gloutonne calculée indépendamment.

    L'effet de l'élagage semble assez remarquable dans le cas de systèmes monétaires raisonables, mais il est insuffisant dans le cas de systèmes comportant beaucoup d'espèces élevées dont les valeurs sont proches (genre ⟨ 200, 199, 198, …, 180, 1 ⟩).