THE MINT PROBLEM

"Tao" begets one; one begets two; two begets three; three begets the myriad creatures.

Laow Zhi, Tao Te Ching (ca. 500 B.C.)

DESCRIPTION: See this page

Source Code: mint.cpp mint.exe

My Algorithm:

(1) Exact Change Problem: Assume we have 5 kinds of coin: 1,5,10,25,50, For each number M, the optimum change number is either OPT(M-1)+1, OPT(M-5)+1, OPT(M-10)+1, OPT(M-25)+1 or OPT(M-50)+1, i.e.  if the coin sets are x1,x2,x3,x4,x5

OPT(M) = min { OPT(M-x1)+1, OPT(M-x2)+1, OPT(M-x3)+1, OPT(M-x4)+1, OPT(M-x5)+1 }

So I use DP (Dynamic Programming) as the following:

coin set: CS[5]

TotalChangeNumber <- 0

M[100] <- {0,0,0,...,0}

for i <- 1 to 99

    min <- INT_MAX

    for j <- 0 to 4

        if CS[j] <= i AND min < M[i-CS[j]] +1

            min <- M[i-CS[j]] +1

    M[i] <- min

    if i mod 5 = 0

        TotalChangeNumber <- TotalChangeNumber + M[i]*4

    else

        TotalChangeNumber <- TotalChangeNumber + M[i]

@

I also use B&B (Branch and Bounce) techniques, I precalculate the Exact Change Number for coin set {1,5,10,25,50}:

Bound <- ExactChangeNumber(1,5,10,25,50)

Then when doing DP, if any time TotalChangeNumber > Bound, I will break the loop and give up this coin set.

Since there must be 1 cent coin, my search space is C(98,4) = 3.6*10^6, and for each coin set I looped 500 times for DP, the complexity is held in 1.8*10^9*C

operations. For a 1.5G Pentium CPU, my running time is 11 secs.

Results:

Total exact change number from 1 cent to 99 cents : 475
Average exact change number(1 cent to 99 cents) :
3.04487
@

(2) In Exchange Problem, my DP method was modified a little. My assumption is for the optimum coin set, there should not be an exchange more than 200 cents, then there is the sixth kind of money: A FREE 100 cents, so the recursive relation becomes:

OPT(M') = min { OPT(M'-x1)+1, OPT(M'-x2)+1, OPT(M'-x3)+1, OPT(M'-x4)+1, OPT(M'-x5)+1, OPT(M'-100) }

Then I fill out M'[-100] to M'[-1] as above, which denoted the best way to make exchange, then add the best way for the money I'm going to pay. Now I looped 1200 times for each coin set (remember there is a sixth "free coin"). As 100 cents is free now, having i cents coin is equivalent to have 100-i cents coin, so it suffice to search from 1 cent to 50 cents. Since 1 cent coin is no longer necessary, the total search space became C(50,5) = 2.1*10^6, leads to 2.5*10^9*C operations. For a 1.5G Pentium CPU, my running time is 27 secs.

Results:

Total exchange number from 1 cent to 99 cents : 328
Average exchange number(1 cent to 99 cents) :
2.10256

back


Chien-I Liao