Implement Program For "Making Change" Using Greedy Design Technique.
Program:
#include<stdio.h>
#include<malloc.h>
int * sort(int *d,int n)
{
inti,j,k;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(d[i]<d[j])
{
k=d[i];
d[i]=d[j];
d[j]=k;
}
}
}
}
int main()
{
intamt,*d,*ans,n,i,flag=0,total=0;
printf("Enter
no of coins:-\n");
scanf("%d",&n);
d=(int
*)malloc(n*sizeof(int));
ans=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
printf("Enter
value of coin no. %d:-\n",(i+1));
scanf("%d",&d[i]);
}
sort(d,n);
printf("enter
amount to get change:-\n");
scanf("%d",&amt);
i=0;
while(amt>0)
{
while(d[i]<=amt)
{
ans[i]++;
amt=amt-d[i];
total++;
}
i++;
if(amt==0)
{
break;
}
if(d[n-1]>amt)
{
flag++;
break;
}
}
if(flag>0)
{
printf("unsucessfull\n");
}
else
{
printf("%d
coins used.\n",total);
for(i=0;i<n;i++)
{
printf("%d
coins used of %d .\n",ans[i],d[i]);
}
}
}
OUTPUT:
No comments:
Post a Comment