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.

two words: brute force

if i have time, i will try and come up with a more efficient method, but even brute force can be elegant... consider this psudo code as i have not compiled it... and i'm positive there are some 1-off errors, but the concept should pull through.

//yes yes... global is bad, but i'm doing it anyway
const int n = USER SPECIFIED;
const int set[n] = {e1, e2 ... en};
//for this algorithm, set should be in ASCENDING ORDER

int greedy(int setsize, int totalamount);
//this will calculate the number of coins the greedy algorithm will generage 
//using the first "setsize" members in "set" for the "totalamount"
//i won't write this since we know what the greedy function does

int lcm();
//this will calculate the lowest common multiple of "set".
//i won't write this since we know how to calculate lowest common multiples.

int main()
{
   int i, j;
   int upperbound = lcm();
   int greedyNumber;

   for (i=upperbound; i>set[n]; i--)
   {
      greedyNumber = greedy(n, i);      
      for (j=n - 1; j>0; j--) 
         if (greedy(j, i) < greedyNumber)
            exit 1;
   }

   exit 0;
}

So... if the program returns a 0, it is an intuitive set, but if it returns a 1 it is not an intuitive set.

this works like so:
1) calculate the greatest possible number you would have to test for, the lowest common multiple of the set.  call this the upperbound.
2) run the greedy algorithm on the whole set to calculate the number of coins to make upperbound.  we'll call the result the greedyNumber.
3) take the greatest element in the set away and run the greedy algorithm for the subset.  
4) if the result is less than the greedyNumber, the set is not intuitive. - STOP WORKING
5) repeat steps 3 and 4 until the set is empty.
6) decrease the upperbound by 1.  if the upperbound is equal to the greatest element in the complete set, you have proven the set to be intuitive - STOP WORKING
7) repeat steps 2-6

so essentially, the whole set is intuitive if it is "greedier" than the subset lacking the greatest element (recursively)...
and that must hold true for all numbers between the greatest number in thet set and the least common multiple of the set.

Posted by steve on 2005-04-08 04:07:31