MAKE CHANGE PROBLEM - GREEDY ALGO

• The change making problem is an optimization problem that asks "What is the minimum number of coins I need to make up a specific total?"
• The input to the Change Making Problem is a sequence of positive integers [d1, d2, d3 ... dn] and T, where di represents a coin denomination and T is the target amount. Assuming an unlimited supply of coins of each denomination, we need to find the number of coins N required to form the given amount

// PROGRAMME FOR MAKE CHANGE PROBLEM
#include<stdio.h>
int findlargest(int c[],int sum,int n)
{
int i;
for(i=0;i<5;i++)
{
if(sum+c[i]<=n)
{
return c[i];
}
}
return -1;
}
void make_change(int n)
{
int c[]={100,25,10,5,1};
int s[n],sum=0,x;
int ind=0,i;
while(sum!=n)
{
x=findlargest(c,sum,n);
if(x==-1)
{
printf("OOPS ! NO SOLUTION FOUND ");
return;
}
s[ind++]=x;
sum+=x;
}
printf("SOLUTION : ");
for(i=0;i<ind;i++)
{
printf("%d ",s[i]);
}

}
main()
{
int n;
printf("ENTER AMOUNT WHICH YOU TO MAKE : ");
scanf("%d",&n);
make_change(n);
}

PRESS HERE TO DOWNLOAD THE PROGRAM