/* Version 1 : on suppose que les quantités de pièces disponibles sont données sous la forme d'une liste ordonnée [E200,E100,E50,E20,E10] ; les quantités de pièces à rendre sont également données sous la forme d'une liste ordonnée */
monnaie1(TotalDonne,TotalDu,[E200,E100,E50,E20,E10],[X200,X100,X50,X20,X10]) :-
        declareDomaines1([E200,E100,E50,E20,E10],[X200,X100,X50,X20,X10]),
        (200*X200 + 100*X100 + 50*X50 + 20*X20 + 10*X10) #= (TotalDonne-TotalDu),
        fd_labeling([X200,X100,X50,X20,X10]).

declareDomaines1([],[]).
declareDomaines1([Ei|LE],[Xi|LX]) :-
        fd_domain(Xi,0,Ei),
        declareDomaines1(LE,LX).


/* Version 2 : si l'on veut exprimer les quantités de pièces disponibles sous une forme plus explicite */
/* monnaie2(TotalDonne,TotalDu,Ldispo,Lrendues) :
    TotalDonne = somme insérée dans le distributeur ;
    TotalDu = somme à payer ;
    Ldispo = liste de termes de la forme "Val:Qte" signifiant qu'il y a dans le distributeur Qte pièces d'une valeur de Val ;
    Lrendues = liste de termes de la forme "Val:Qte" signifiant qu'il faut rendre Qte pièces d'une valeur de Val. */
monnaie2(TotalDonne,TotalDu,Ldisponibles,Lrendues) :-
        declareDomaines2(Ldisponibles,Lrendues,Lvariables),
        construitExpression2(Lrendues,Expr),
        Expr #= TotalDonne-TotalDu,
        fd_labeling(Lvariables).

declareDomaines2([],[],[]).
declareDomaines2([Vali:Ei|LE],[Vali:Xi|LX],[Xi|LV]) :-
        fd_domain(Xi,0,Ei),
        declareDomaines2(LE,LX,LV).

construitExpression2([Val:X],Val*X).
construitExpression2([Val:X|L],Val*X + Expr) :- construitExpression2(L,Expr).



/* Version 3 : On peut exprimer le fait que l'on souhaite trouver une solution qui minimise le nombre de pièces rendues.
    On utilise pour cela le prédicat Gnu-Prolog fd_minimize/2 */
monnaie3(TotalDonne,TotalDu,Ldisponibles,Lrendues) :-
        declareDomaines2(Ldisponibles,Lrendues,Lvariables),
        construitExpression3(Lrendues,Expr,Somme),
        Expr #= TotalDonne-TotalDu,
        NbPieces #= Somme,
        fd_minimize(fd_labeling(Lvariables),NbPieces).

construitExpression3([Val:X],Val*X,X).
construitExpression3([Val:X|L],Val*X + Expr,X+Somme) :- construitExpression3(L,Expr,Somme).

/* Version 4 : On peut également exprimer le fait que l'on souhaitetrouver une solution qui maximise le plus petit nombre de pieces restant pour chaque valeur. On utilise pour cela le prédicat fd_maximize/2 */
monnaie4(TotalDonne,TotalDu,Ldisponibles,Lrendues) :-
        declareDomaines2(Ldisponibles,Lrendues,Lvariables),
        construitExpression4(Ldisponibles,Lrendues,Expr,Min),
        Expr #= TotalDonne-TotalDu,
        NbMinPieces #= Min,
        fd_maximize(fd_labeling(Lvariables),NbMinPieces).

construitExpression4([Val:E],[Val:X],Val*X,E-X).
construitExpression4([Val:E|LE],[Val:X|LX],Val*X + Expr,min(E-X,Min)) :-
        construitExpression4(LE,LX,Expr,Min).