Subsections

Example: Send Most Money

In section 4.2.3 we searched for a solution to the Send More Money problem. The send Send Most Money problem has more than one solution and we want to find the best one.

Script

fun smm space =
  let
    (* I use o' because o is an operator *)
    val letters as #[s, e, n, d, m,o', t, y] = 
        FD.rangeVec(space, 8,(0,9))
    val money = FD.range(space,(0, 98765))
    (* better function *)
    fun better (current, lastSolution) =
         post (current, FD(money) `> 
          `(FD.Reflect.value(lastSolution,money)),FD.BND)
  in
    FD.distinct (space, letters, FD.DOM);
    post (space, FD(s) `<> `0, FD.DOM);
    post (space, FD(m) `<> `0, FD.DOM);
    post (space, `1000 `* FD(s) `+ `100 `* FD(e) `+ 
                 `10 `* FD(n) `+ FD(d) `+  `1000 `* FD(m)`+ 
                 `100 `* FD(o') `+ `10 `* FD(s) `+ FD(t)
             `= `10000 `* FD(m) `+ `1000 `* FD(o') `+ `100 `* 
                  FD(n) `+ `10 `* FD(e) `+ FD(y), FD.DOM);
    post (space, FD(money)`= `10000 `* FD(m) `+ `1000 `* FD(o')
            `+ `100 `* FD(n) `+ `10 `* FD(e) `+ FD(y), FD.DOM);
    FD.branch (space, letters, FD.B_SIZE_MIN, FD.B_MIN);
    ({s, e, n, d, m, o', t, y}, better)
  end

The procedure better in listing 23 ensures that the value of money is maximized. Again, you use

Explorer.exploreBest(smm)
to get a search tree where the value of money in every solution space is higher than the one in a solution space before.



Andreas Rossberg 2006-08-28