Make A Change Using Greedy Algorithm In C Program

#include< stdio.h>
#include< conio.h>
int C[]={1,5,10,25,100};


void make_change(int n);
int bestsol(int,int);

void main()
{
 int n;
 clrscr();
 printf("\n------------------------------------------------");
 printf("\n       MAKING CHANGE USING GREEDY ALGORITHM     ");
 printf("\n------------------------------------------------");
 printf("\n Enter amount you want:");
 scanf("%d",&n);
 make_change(n);

getch();
}


void make_change(int n)
{

 int S[100],s=0,x,ind=0,i;
 printf("\n----------------AVAILABLE COINS-----------------\n");

 for(i=0;i<= 4;i++)
  printf("%5d",C[i]);

 printf("\n------------------------------------------------");
 



while(s!=n)
 {
  x=bestsol(s,n);
  if(x==-1)
  {}
  else
  {
   S[ind++]=x;
   s=s+x;
  }
 }
 printf("\n-------------MAKING CHANGE FOR %4d-------------",n);
 for(i=0;i < ind;i++)
 {
  printf("\n%5d",S[i]);
 }
 printf("\n------------------------------------------------");
}

int bestsol(int s,int n)
{
 int i;
 for(i=4;i>-1;i--)
 {
  if((s+C[i]) <= n)
   return C[i] ;
 }
 return -1;
}


OUTPUT



-------------------------------------------------------------------------------
       MAKING CHANGE USING GREEDY ALGORITHM
-------------------------------------------------------------------------------
 Enter amount you want:196

---------------------------AVAILABLE COINS-------------------------
    1    5   10   25  100
-------------------------------------------------------------------------------
---------------------MAKING CHANGE FOR  196-------------------
  100
    25
    25
    25
    10
    10
      1
-------------------------------------------------------------------------------