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 4-member 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 A-Z
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 2005-03-31 14:18:05