DouKaku?

coins([500,100,50,10,5,1]).

change(Sum,C):-coins(Coins),change(Coins,Sum,C).
change([],_,[]).
change([Co|Cos],Sum,C):-Co>Sum,change(Cos,Sum,C),!.
change([Co|Cos],Sum,[c(Co,C)|Cs]):-C is Sum // Co,Sums is Sum mod Co, change(Cos,Sums,Cs).

takeout([],[],[]).
takeout([c(Co,C)|Pos],Pa,R):-countUp(C,C1),plus(C2,C1,C),C1>=0,C2>=0,
                             (C1==0->Pa=Pas;Pa=[c(Co,C1)|Pas]),
                             (C2==0->R=Rs;R=[c(Co,C2)|Rs]),
                             takeout(Pos,Pas,Rs).

countUp(N,I):-countUp(N,0,I).
countUp(N,S,S):-S=<N.
countUp(N,S,I):-S<N,Ss is S + 1,countUp(N,Ss,I).

minCoin([A],[A]):-!.
minCoin([a(Ca,Pa)|As], B) :-
        minCoin(As, [a(C,P)|Ps]),
        (Ca<C->B=[a(C,P)];
               (Ca==C->B=[a(C,P),a(Ca,Pa)|Ps];
                       B=[a(C,P)|Ps])).

total([],0).
total([c(Co,C)|Cs],X):-total(Cs, Xs), X is Xs + Co * C.

try(Sum, Pocket, Pay, Rest, C) :-
        takeout(Pocket, Pay, Rest0),
        total(Pay, Total),
        Total >= Sum,
        plus(Change, Sum, Total),
        change(Change, Change0),
        diffCoin(Pay,Change0),
        appendCoin(Rest0,Change0,Rest),
        countCoin(Rest,C).

coinNumber(c(_,N),N).
coinName(c(N,_),N).

appendCoin([],X,X).
appendCoin([c(C,N)|Cs],R0,R):-appendCoinSub(C,N,R0,R1),appendCoin(Cs,R1,R).

appendCoinSub(C,N,[],[c(C,N)]).
appendCoinSub(C,N,[c(C,M)|Cs],[c(C,L)|Cs]):-L is N + M,!.
appendCoinSub(C,N,[Cx|Cs],[Cx|Rs]):-appendCoinSub(C,N,Cs,Rs).

diffCoin(X,Y):-maplist(coinName,X,Xn),maplist(coinName,Y,Yn),intersection(Xn,Yn,[]).

countCoin([],0).
countCoin([c(_,C)|Cs],X) :- countCoin(Cs,Xs), X is Xs + C.

findAns(Sum,Before,As):-findall(a(C,Pay),try(Sum,Before,Pay,_,C),As0),minCoin(As0,As).

:-findAns(147,[c(1,2),c(10,4),c(100,3)],A),writeln(A),halt.