/*
Two coin applications in Picat.
From "The ECLiPSe Book" pages 99f and 234 ff
The solution in ECLiPSe is at page 236.
"""
What is the minimum number of coins that allows one to pay _exactly_
any amount smaller than one Euro? Recall that there are six different
euro cents, of denomination 1, 2, 5, 10, 20, 50
"""
There are 4 optimal solutions (8 coins):
x=[1,2,1,2,1,1]
x=[1,2,2,1,1,1]
x=[2,1,1,2,1,1]
x=[2,1,2,1,1,1]
The other application (go2/0) is to create the denominations
which minimize the number of coins used in this way.
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
go =>
% the different coin values
Variables = [1,2,5,10,25,50],
N = length(Variables),
Xs = new_list(N),
Xs :: 0..99,
% total number of the coins used
NumCoins :: 0..99,
NumCoins #= sum(Xs),
% This is the "main loop":
% Checks that all changes from 1 to 99 can be made.
% To be honest I have forgotten exactly how
% the ECLiPSe solution looked like.
% Here is one way.
foreach(J in 1..99)
Tmp = new_list(N),
Tmp :: 0..99,
scalar_product(Variables,Tmp,J),
% Ensure that we don't use more coins than in X[I]
foreach(I in 1..N)
Tmp[I] #=< Xs[I]
end
end,
solve($[min(NumCoins)], Xs),
writeln(num_coins=NumCoins),
writeln(x=Xs),
nl.
scalar_product(A, X, Product) =>
Product #= sum([A[I]*X[I] : I in 1..A.length]).
increasing(List) =>
foreach(I in 2..List.length) List[I-1] #=< List[I] end.
do_coins(J,Xs,Variables,N) =>
Tmp = new_list(N),
Tmp :: 0..99,
scalar_product(Variables,Tmp,J),
foreach(I in 1..N) Tmp[I] #=< Xs[I] end.
%
% A related problem:
%
% Is there a set of coin denominations which make it possible to change
% into 1..99 with less than 8 coins?
%
% Answer: Yes, there is. For example the following configuration:
%
% num_coins:7
% variables:[1,2,3,6,12,25,50]
% x:[1,1,1,1,1,1,1]
%
% Though, it come with a cost of using 7 different coin denominations.
%
% Also, we can see that there is a set with just 5 different
% denominations for the 8 coin change. However, it requires that
% more than one coin of some of the denominations
%
% This is done by comment this constraint:
% NumCoins #=< 8,
%
% Result:
% num_coins:8
% variables:[1,2,4,11,33]
% x:[1,1,2,2,2]
%
go2 =>
% Number of coin denominations
% Note: It increases with each failure to
% solve the instance.
N :: 1..10,
indomain(N),
write(n=N),nl,
% we assume that there are no coin of a denomination larger than 50.
Variables = new_list(N),
Variables :: 1..50,
all_different(Variables),
increasing(Variables),
Xs = new_list(N),
Xs :: 1..2, % use either 1 or two coins
% total number of the coins used
% in the exchange
% optimize over total number of coins
NumCoins #= sum(Xs),
% optimize over number of denominations
% NumCoins #= sum([1 : _ in Xs]),
% can we manage with less than 8 coins?
NumCoins #< 8,
foreach(J in 1..99) do_coins(J,Xs,Variables,N) end,
% search
Vars = Xs ++ Variables,
solve([$min(NumCoins), ff],Vars),
% output
writeln(num_coins=NumCoins),
writeln(variables=Variables),
writeln(x=Xs), nl, nl.