import fr.upd.*;
import java.util.*;

/**
 * Un programme permettant de déterminer si étant donné un ensemble
 * ordonné de pièces de monnaies, il est possible d'ne sélectionner
 * certaines pour obtenir exactement une somme donnée.
 * Attention, les pièces peuvent apparaître plusieurs fois mais chaque
 * pièce est unique!
 *
 * Exercice : combien de possibilités existe t-il si l'on compte
 *            naïvement ?
 * Exercice : Implémenter un algorithme de recherche de solution
 *            naïf (qui essaie vraimeent TOUTES les possibilités)...
 * Exercice : calculer et afficher le gain en nombre d'essais entre
 *            une version naïve et la version avec backtracking...
 * Exercice : transformer l'algorithme de backtracking de sorte que
 *            l'on s'arrête à la première possibilité
 * Exercice : transformer l'algorithme de backtracking de sorte qu'on
 *            affiche non pas le numéro des pièces utilisées pour une
 *            solution, mais la valeur des pièces.
 * Exercice : transformer l'algorithme de backtracking de sorte qu'on
 *            affiche à la fois le numéro des pièces et leur indice
 *            dans la poche pour une solution trouvée.
 * Exercice : transformer l'algorithme de backtracking de sorte que
 *            que deux solutions sont différentes si les ensembles de
 *            pièces sont différents (i.e. on ne distingue plus deux
 *            pièces de même valeur).
 */
public class Monnaie {
  /**
   * Le contenu de la poche
   */
  public static int [] poche = {
    20, 5, 10, 50, 5, 1, 1, 2, 50, 5, 5, 5, 20
  };
  /**
   * On compte le nombre d'essais
   */
  private static int nbEssais;
  /**
   * On suppose avoir déterminé la présence ou non des pièces d'indices
   * 0 à i-1, maintenant il faut essayer avec la pièce i ou non.
   * Chaque fois qu'on essaie avec une pièce, on diminue la valeur à
   * atteindre d'autant.
   */
  public static void resoud(int i,int valeur,Stack<Integer> solution) {
    // Si on atteint une valeur négative c'est que notre choix
    // précédent était mauvais (pièce de valeur trop grande)
    if (valeur<0)  { nbEssais++; return; }
    // Si la valeur est nulle, on a gagné!
    if (valeur==0) { nbEssais++; System.out.println("Une solution "+solution); return; }
    // S'il n'y a plus de pièces c'est raté...
    if (i==poche.length) { nbEssais++; return; }
    // On essaie avec la pièce d'indice i, en l'ajoutant à la
    // solution
    solution.push(i);
    resoud(i+1,valeur-poche[i],solution);
    // On essaie sans la pièce...
    solution.pop();
    resoud(i+1,valeur,solution);
    // Sinon on « revient sur nos pas »
    return;
  }
  public static void main(String []args) {
    nbEssais = 0;
    Stack<Integer> solution = new Stack<Integer>();
    resoud(0,46,solution);
    System.out.println("Nombre de tests "+nbEssais);
  }
}