Suppose that a country adopts coins of values 1 10 and 21 Do

Suppose that a country adopts coins of values 1, 10, and 21. Does the greedy algorithm to give change always give the fewest number of coins? Prove it or give the smallest counter example.

Solution

First let us proceed with a sample greedy algorithm that we can implement easily using C :

int change(int amount) {
   int c21, c10, c1, totalCount;
  
   c21 = amount / 21;
   amount = amount % 21;
  
   c10 = amount / 10;
   amount = amount % 10;
  
   c1 = amount / 1;

   totalCount = c1 + c10 + c21;
   return totalCount;
}

We can prove using counter example that greedy method fails in certain cases:
     Let us consider an example where amount = 30
             following the greedy method we shall have 1 coin of amount 21 and 9 coins of amount 1, thus total of 10 coins
             but looking into the simple problem we can say 3 coins of value 10 could have solved the problem.
     thus we can say greedy method fails.

To solve the problem we can use a naive method that compares all possible changes and returns the final result. the following code segment solves the problem well but with higher complexity.

int change(int amount) {
   int i, j, remainingAmount21, remainingAmount10, c21, c10, c1, count;
   count = MAXINTEGER;
   for ( i = 0; i<= amount/21; i++) {
       remainingAmount21 = amount - 21*i;
       for (j = 0; j<=remainingAmount/10; j++) {
           remainingAmount10 = remainingAmount21 - 10*j;
           if( (i + j + remainingAmount10) < count) {
               c21 = i;
               c10 = j;
               c1 = remainingAmount10;
               count = c21 + c10 + c1;
           }
       }
   }
   return count;
}