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-**

Results:

Total exchange number from 1 cent to 99
cents :
328

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

Chien-I Liao