🚀 go-pugleaf

In article <1993Jan7.141322.22240@ecrc.de> thom@ecrc.de writes:

#  min_coins(Value,Coins):-
#  	list(Coins),
#  	sum_coins(Coins,Value).
#  
#  list([]).
#  list([X|L]):- list(L).
#  
#  sum_coins([],0).
#  sum_coins([Coin|Coins],Sum):-
#  	coin(Coin,Value),
#  	Value =< Sum,
#  	NewSum is Sum-Value,
#  	sum_coins(Coins,NewSum).
# ...
# coins detail omitted


This is a short solution, but it is really just a neat way of doing
iterative deepening.  To be honest, I hadn't thought of doing it quite
this way.  However, it might be spectacularly inefficient.  Supposing
the fewest coins needed to make up some sum is seven.  This algorithm
will try a large number of combinations of 2 coins, then 3, then 4, then
5, then 6, before finding the optimal solution.  So this does not really
qualify as the Ultimate Answer. 

Adding a clause

   sum([],X) :-
	X > 0,
	write('failed'),
	nl.

will print the word `failed' for each unsuccessful combination.

Ken Johnson
-- 
Son, all the pretty, intelligent, healthy     #    Ken Johnson, AIAI,
young women are taken. It's a basic rule of   #    80 South Bridge, Edinburgh
the universe, and if you don't like it, go    #    Tel 031-650 2756 
somewhere else.        -- my dad  1906-1992   #    Fax 031-650 6513