Determine the minimum number of coins required for giving a change using greedy approach

Question

As an assignment for my course on Design and Analysis of Algorithms, I was asked to determine the minimum number of coins required for giving a change, using a greedy approach. I came up with this intuitive approach:

#include<stdio.h>
#include<stdlib.h>

int main(){
  int hundreds=0,tens=0,ones=0,sum=0;

  printf("Enter a sum of money in range 1 to 999\n");
  scanf("%d",&sum);
  while(sum!=0) {
    if (sum<10&&sum>=1){
      ones=sum/1;
      sum-=ones;
    }
    else if(sum>=10&&sum<100){
      tens=sum/10;
      sum-=tens*10;
    }
    else if(sum>=100&&sum<=999){
      hundreds=sum/100;
      sum-=hundreds*100;
    }
    else{
      printf("Error");
      exit(0);
    }
  }

  printf("%d $100, %d $10, %d $1",hundreds,tens,ones);
  return 0;
}

Is this approach greedy? How do I prove that the program is correct and uses the greedy approach?

Answer 1

This is indeed greedy approach but you need to reverse the order of if-then-else. In general, greedy means to consume at the current moment the biggest quantity that you can consume.

You need to check first for the biggest coin. There is no need for while-loop.

if(sum>=100) {
  hundreds=sum/100;
  sum-=hundreds*100;
}
if(sum>=10){
  tens=sum/10;
  sum-=tens*10;
} 
ones = sum;