Wednesday, September 26, 2018

Implement Program for “Making Change” using Greedy design technique

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

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

int main()
{
        int n;
        printf("Enter amount you want: ");
        scanf("%d",&n);
        make_change(n);
        return 0;
}

void make_change(int n)
{

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

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

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

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

No comments:

Post a Comment