change.pl

:- table fewest_coins/3.

fewest_coins(_, 0, []).
fewest_coins(Coins, Target, Change) :-
    Target > 0,
    convlist(solve_subproblem(Coins, Target), Coins, Solutions),
    min_member(length_leq, Change, Solutions).

length_leq(A, B) :- length(A, LenA), length(B, LenB), LenA =< LenB.

solve_subproblem(Coins, Target, Coin, Change) :-
    plus(SubTarget, Coin, Target),
    fewest_coins(Coins, SubTarget, SubChange),
    Change = [Coin | SubChange].

in.txt

fewest_coins([1, 5, 10, 25], 1, Change).
fewest_coins([1, 5, 10, 25, 100], 25, Change).
fewest_coins([1, 5, 10, 25, 100], 15, Change).
fewest_coins([1, 4, 15, 20, 50], 23, Change).
fewest_coins([1, 5, 10, 21, 25], 63, Change).
fewest_coins([1, 2, 5, 10, 20, 50, 100], 999, Change).
fewest_coins([2, 5, 10, 20, 50], 21, Change).
fewest_coins([4, 5], 27, Change).
fewest_coins([1, 5, 10, 21, 25], 0, Change).
fewest_coins([5, 10], 3, Change).
fewest_coins([5, 10], 94, Change).
fewest_coins([1, 2, 5], -5, Change).

out.txt

Change = [1].

Change = [25].

Change = [5, 10].

Change = [4, 4, 15].

Change = [21, 21, 21].

Change = [2, 2, 5, 20, 20, 50, 100, 100, 100|...].

Change = [2, 2, 2, 5, 10].

Change = [4, 4, 4, 5, 5, 5].

Change = [].

false.

false.

false.

run.sh

swipl -f change.pl <in.txt >out.txt