If you must pay an amount in coins, the "intuitive" algorithm is: pay as much as possible with the largest denomination coin, and then go on to pay the rest with the other coins. For example, if there are 25, 5 and 1 cent coins, to pay someone 32 cents, you'd first give him a 25 cents coin, then one 5 cent coin, and finally two 1 cent coins.)
However, this doesn't always end paying with as few coins as possible: if we had 25, 10 and 1 cent coins, paying 32 cents with the "intuitive" algorithm would use 8 coins, while three 10 cent coins and two 1 cent coins would be better.
We can call a set "intuitive", if the "intuitive algorithm" always pays out any amount with as few coins as possible.
The problem: give an algorithm that allows you to decide that {25,5,1} is an "intuitive" set, while {25,10,1} isn't.
(In reply to
re(2): There's more to it.... (solution? spoiler?)  larger sets by Charlie)
I've written a program to compare the results of merely trying all multiples of each denomination up to the LCM of all the denominations, seeing if that multiple is matched by the number found by the greedy algorithm, with the results of an exhaustive search of the best way of obtaining any value from 1 to the LCM of all the denominations. I tried it with 5 denominations in each set, and found, for example:
test every mult of every den
No problem found.
Full testFailed at 9 : 2 vs 3
7 5 4 3 1
showing that checking all the multiples of each denomination against the greedy algorithm did not detect the lack of intuitiveness of the set {7, 5, 4, 3, 1}. Although the full test detected nonintuitiveness at 9, where 5+4 beats 7+1+1, the old test did not detect this, as its trial of 9 consisted of 3+3+3, which did not beat 7+1+1. In fact the 4member set {7, 5, 4, 1} fails at 9 for the same reason and the former test would not even have tried 9.
The "full test" is in the program that follows under the PRINT "Full test" statement through the FOR value = 1 to l...NEXT loop. If flag2 is set to 1 the set is not intuitive, otherwise it is intuitive. I've bolded the text of this full test.
The method, in words, is to build a list of how many coins are required for each total value from 1 to the LCM of all the denominations. (I hope that's sufficiently far to go.) The way this is done, for a particular denomination, is to try by starting out with, in turn, each of the available denominations that does not exceed the total value. This leaves a certain remaining value. Since that value is lower, we've already figured the best way of getting that lower value, and we add 1 to that number of coins needed. As said, this is tried for each of the possible starting denominations to get the best way for this total value (whichever is lowest), and then we go on to the next. As each is found, it is compared with the results of the greedy algorithm. If a discrepancy is found in the number of coins, it is reported.
DECLARE FUNCTION gcd# (x#, y#)
DECLARE FUNCTION lcm# (x#, y#)
DECLARE FUNCTION intuit# (amt#)
DEFDBL AZ
DIM SHARED den(15)
DIM SHARED noDens
noDens = 5
den(noDens) = 1
FOR i = 1 TO noDens
PRINT den(i);
NEXT
PRINT
FOR d1 = 5 TO 70
den(1) = d1
FOR d2 = 4 TO d1  1
den(2) = d2
FOR d3 = 3 TO d2  1
den(3) = d3
FOR d4 = 2 TO d3  1
den(4) = d4
l = 1
FOR i = 1 TO noDens
l = lcm(l, den(i))
NEXT
CLS
PRINT "test every mult of every den"
flag1 = 0
FOR d = 1 TO noDens
num = 0
FOR a = den(d) TO l STEP den(d)
num = num + 1
IF intuit(a) > num THEN
PRINT "Failed at "; num; " x "; den(d); " ("; a; ")."
flag1 = 1
EXIT FOR
END IF
NEXT a
NEXT d
IF flag1 = 0 THEN PRINT "No problem found."
PRINT
PRINT "Full test"
REDIM SHARED nextCoin(l) AS INTEGER
REDIM SHARED numToDo(l) AS INTEGER
flag2 = 0
FOR value = 1 TO l
bestCt = value + 1
FOR d = 1 TO noDens
IF den(d) = value THEN
nextCoin(value) = value
numToDo(value) = 1
bestCt = 1
EXIT FOR
ELSEIF den(d) < value THEN
valueRem = value  den(d)
possible = 1 + numToDo(valueRem)
IF possible < bestCt AND numToDo(valueRem) > 0 THEN
nextCoin(value) = den(d)
numToDo(value) = possible
bestCt = possible
END IF
END IF
NEXT
IF bestCt > value THEN
nextCoin(value) = 0
numToDo(value) = 0
END IF
d = nextCoin(value): ct = 1: valueRem = value  d
DO
IF valueRem = 0 THEN EXIT DO
IF nextCoin(valueRem) = d THEN
ct = ct + 1
ELSE
ct = 1
END IF
d = nextCoin(valueRem): valueRem = valueRem  d
LOOP
IF numToDo(value) < intuit(value) THEN
PRINT "Failed at "; value; ":"; numToDo(value); "vs"; intuit(value)
flag2 = 1
EXIT FOR
END IF
NEXT
IF flag1 <> flag2 THEN
PRINT d1, d2, d3, d4, 1: DO: LOOP UNTIL INKEY$ > ""
END IF
NEXT
NEXT
NEXT
NEXT
FUNCTION gcd (x, y)
dnd = x: dvr = y: IF dnd < dvr THEN SWAP dnd, dvr
DO
q = dnd \ dvr
r = dnd MOD dvr
IF r = 0 THEN EXIT DO
dnd = dvr: dvr = r
LOOP
gcd = dvr
END FUNCTION
FUNCTION intuit (amt)
t = 0: amtLeft = amt
FOR i = 1 TO noDens
q = amtLeft \ den(i)
amtLeft = amtLeft MOD den(i)
t = t + q
NEXT
intuit = t
END FUNCTION
FUNCTION lcm (x, y)
lcm = x * y / gcd(x, y)
END FUNCTION

Posted by Charlie
on 20050331 14:18:05 