Implement Program for “Making Change” using Dynamic Programming.


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int min(int a,int b)
{
            if(a<b)
            {
                        return a;
            }
            else
            {
                        return b;
            }
}

void main()
{
            int ncoins,change,i,j,**c;
            int denom[10];
            clrscr();
            printf("enter no.of coins:");
            scanf("%d",&ncoins);
            printf("enter the value of ncoins:\n");
            for(i=0;i<ncoins;i++)
            {
                        scanf("%d",&denom[i]);
            }
            printf("enter the amount to get the change:");
            scanf("%d",&change);

            *c=(int *)malloc(ncoins*sizeof(int));
            for(i=0;i<change;i++)
            {
                        *(c+i)=(int *)malloc((change+1)*sizeof(int));
            }
            for(i=0;i<ncoins;i++)
            {
                        c[i][0]=0;
            }

            for(i=0;i<ncoins;i++)
            {
                        for(j=1;j<=change;j++)
                        {

                                    if(i==0 && j<denom[0])
                                    {
                                                c[i][j]=infinite;
                                    }
                                    else if(i==0)
                                    {
                                                if(c[i][j-denom[0]]==infinite)
                                                {
                                                            c[i][j]=infinite;
                                                }
                                                else
                                                {
                                                            c[i][j]=1+c[i][j-denom[0]];
                                                }
                                    }
                                    else if(j<denom[i])
                                    {
                                                c[i][j]=c[i-1][j];
                                    }
                                    else
                                    {
                                                c[i][j]=min(c[i-1][j],1+c[i][j-denom[i]]);
                                    }
                        }
            }
            printf("Table:\n");
            for(i=0;i<ncoins;i++)
            {
                        for(j=1;j<=change;j++)
                        {
                                    printf("\t%d",c[i][j]);
                        }
                        printf("\n");
            }

            getch();
}

Comments

Post a Comment

Popular posts from this blog

Write user defined functions for the following sorting methods and compare their performance by time measurement with random data and Sorted data.

Image
SELECTION SORT: #include<stdio.h> #include<conio.h> #include<math.h> #include<time.h> #define n 10000 void selection_sort(int[]); unsigned long int count=0; void main() {             int a[n];             int choice,i;             clrscr();             printf("1.Sorted Data  2.Random Data \n");             scanf("%d",&choice);             switch(choice)             {                         case 1:    ...
Read more

Implement functions to print nth Fibonacci number using iteration and recursive method.

Image
Implement functions to print nth Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. (Fibonacci series 1, 1, 2, 3, 5, 8…..  Here 8 is the 6th Fibonacci number) #include<stdio.h> #include<conio.h> int iteration(int); int recursive(int); int count=0; void main() { int n,choice,ans; clrscr(); printf("\nenter nth number : "); scanf("%d",&n); printf(“\n==iteration==”); ans=iteration(n); printf(“\nans=%d\ncount=%d”,ans,count); printf(“\n\n==recursive==”); ans=recursive(n); printf("\nans=%d\ncount=%d",ans,count); getch(); } int iteration(int n) { int f=1,s=1,t,i; count++;   count++; for(i=3;i<=n;i++) { t=f+s; count++; f=s; count++; s=t; count++; } count++; return t; } int recursive(int n) { count++; if(n==0 || n==1) { cou...
Read more

Implement a function of sequential search and count the steps executed by function on various inputs for best case and worst case. Also write complexity in each case and draw a comparative chart.

#include<stdio.h> #include<conio.h> #define size 10 unsigned long count=0; void linear_search(int a[],int no) {       int i;       count++;       for(i=0;i<size;i++)       {                   count++;                   count++;                   if(a[i]==no)                   {                               count++;         ...
Read more