Steve Hunter did an excellent analysis of the problem and then
produced an *extremely* fast version, writen in Python, that
he shared with me. I, uh, 'borrowed' some of his analysis and
backed it into the last Icon version I posted. The result
is so fast that I can't time the "13 coins for $1.10" problem -
it runs faster than my timer resolution. However, I can time
a "52 coins for $4.40" solution - ~20ms! The previous version
takes over 5 seconds. Thanks, Steve!
I've attached the latest (and my last, I promise!) solution.
As a rough measure, the previous version made 1913 calls to
the genCoins() procedure in the 13/110 problem - this one makes
53.
-Steve
--
Steve Wampler [EMAIL PROTECTED]
The gods that smiled upon your birth are laughing now. -- fortune cookie
global cMap, nMap, min_denom, min_value
# Given a monetary amount TARGET in US cents, and a number N of
# coins, generates all possible combinations of N US coins that
# exactly match TARGET cents.
#
procedure main(args)
start := &time
target := integer(args[1]) | 110
nCoins := integer(args[2]) | 13
# Precompute a few constant values
# US coin demoninations...and their worth in cents.
allCoins := "DFQdnp"
cMap := table()
cMap["D"] := 100; cMap["F"] := 50; cMap["Q"] := 25
cMap["d"] := 10; cMap["n"] := 5; cMap["p"] := 1
# Worth of the 'next' denomination for each of the above
nMap := table()
nMap["D"] := 50; nMap["F"] := 25; nMap["Q"] := 10
nMap["d"] := 5; nMap["n"] := 1
# Minimum denomination and its worth
min_denom := allCoins[-1]
min_value := cMap[min_denom]
# Now solve the problem
write("Combinations of ",nCoins," US coins to make ",target," cents:")
every i := 1 to *allCoins do {
coin := allCoins[i]
coins := allCoins[i:0]
process(genCoins(genDenom(coin,target,nCoins),nCoins,target,coins))
}
write(&errout, "Time: ",&time-start)
end
# Generate solutions.
#
procedure genCoins(s, i, t, coins)
if (i < *s) | (t < 0) then fail
cValue := cMap[s[1]]*(*s)
if i = *s then return (t = cValue, s)
else {
t -:= cValue
every k := 2 to *coins do {
suspend s || genCoins(genDenom(coins[k],t,i-*s),i-*s,t,coins[k:0])
}
}
end
# Generate longer sequences of a given demonination, stop when it
# makes sense to stop (too many coins or too much money).
#
procedure genDenom(c, t, nc)
if c == min_denom then return (t=(min_value*nc), repl(c,nc))
value := cMap[c]
nValue := nMap[c]
max_c := (nc > ((t-(min_value*nc)) / (value-min_value))) | nc
min_c := (0 < (t-nValue*nc)/(value-nValue)) | 1
coins := repl(c, min_c-1)
suspend (min_c to max_c, coins ||:= c)
end
# Have a solution, output it.
# (Could produce a more human-friendly form here, if desired.)
#
procedure process(answer)
write("\t",answer)
end
