Example: Changing Money

Problem Specification

Given bills and coins of different denominations and an amount, select a minimal number of bill and coins to pay . One instance of the problem assumes that we want to pay the amount of 1.42, and that we have 6 one dollar bills, 8 quarters (25 cents), 10 dimes (10 cents), 1 nickel (5 cents), and 5 pennies (1 cent).

Viewpoint

To avoid conversions, we assume that the amount to be paid and all denominations are specified in the same currency unit (e.g., cents). The data is specified by variables a₁,..., a_k specifying the available denominations d_i and the number a_i of available respective coins or bills.

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 $\leq$ C_i $\leq$ a_i. Moreover, we must satisfy the constraint

d₁*C₁ + d₂*C₂ +...+ d_k*C_k = amount

Branching Strategy

We branch on the variables C₁, C₂,..., where we give precedence to larger denominations and, with second priority, to larger values.

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