The viewpoint has a variable for ever available denomination saying how many
of the corresponding bills or coins we will use to pay the amount. For all i,
we must have
0
Ci
ai
d1*C1 + d2*C2 +...+ dk*Ck = amount
Branching Strategy
We branch on the variables
C1, C2,...
Script
In Listing 10
The procedure changeMoney takes three parameters. Besides the standard
argument space, it needs a vector of records - billsandcoins
where each field specifies a denomination's value in cents and how many
coints of that denomination are available. The second argument
amount specifies the result of the linear equation mentioned above.
It is assumed that the
bills and coins are specified in denomination decreasing order.
(* billsandcoins is a vector of pairs where the first component
specifies the value of a coin in cents and the second the
the amount of available coins *)
val billsandcoins = #[{incents=100,avail=6},
{incents=25,avail=8},
{incents=10,avail=10},
{incents=5,avail=1},
{incents=1,avail=5}];
(* amount specifies the amount of money you have to pay*)
val amount = 142;
fun changeMoney(bac:{avail:int,incents:int}vector) amount space =
let
val denoms = Vector.map(fn x =>
FD.range(space,(0,#avail(x))))(bac)
in
FD.linear(space,VectorPair.zip(Vector.map
(fn x =>(#incents(x)))bac,denoms),
FD.EQ,amount,FD.DOM);
FD.branch(space,denoms,FD.B_NONE,FD.B_MAX);
{dollars=Vector.sub(denoms,0),quarters=Vector.sub(denoms,1),
dimes=Vector.sub(denoms,2),nickels=Vector.sub(denoms,3),
pennies=Vector.sub(denoms,4)}
end