Error in Making Change using Dynamic Programming in c

Question

Well i have tried it many time and still unable to find the error in the code below it is making change proble using dynamic programming need help to eliminate the wrong output and if possible plz tell me whether this is ideal way of solving this problem using dynamic programming :

Code

    #include<stdio.h>
    int min(int a , int b)
    {
        if(a>b)
        {
            return b;
        }
        else if (b>a)
        {
            return a;
        }
    }
    void making_change(int n,int c,int value[])
    {
        int i,j,m[n][c];
        for(j=1;j<=c;j++)
        {
            m[0][j]=9999;
        }
        for(i=0;i<=n;i++)
        {
            m[i][0]=0;
        }
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= c; j++)
            {
                if (j-value[i-1]<0)
                {
                    m[i][j]=m[i-1][j];
                }
                else
                {
                    m[i][j]=min(m[i-1][j],1+m[i][j-value[i-1]]);
                }
            }
        }
        printf("The number of required coins are : %d",m[n][c]);
    }
    void main()
    {
        int i,c,n;
        printf("Enter the number of different coins : ");
        scanf("%d",&n);
        int value[n];
        printf("Enter the total cost : ");
        scanf("%d",&c);
        printf("********************Enter the values of different coins******************** \n");
        for(i=0;i<n;i++)
        {
            printf("Enter the value of coin %d : ",i+1);
            scanf("%d",&value[i]);
        }
        making_change(n,c,value);
    }

**Wrong Output is : **

Enter the number of different coins : 3
Enter the total cost : 8
********************Enter the values of different coins******************** 
Enter the value of coin 1 : 1
Enter the value of coin 2 : 4
Enter the value of coin 3 : 6
The number of required coins are : 0

In correct case the number of coins should be 2 that is two coins of value 4. It is getting wrong in finding the value of m(1,1) it's coming 999 but should be 1.

Correct Output is :

Enter the number of different coins : 3
Enter the total cost : 8
********************Enter the values of different coins******************** 
Enter the value of coin 1 : 1
Enter the value of coin 2 : 4
Enter the value of coin 3 : 6
The number of required coins are : 2

Answer 1

I can see several issues with your code:

1. Your min function doesn't handle the case when both values are equal. You should add a return for that case.
2. The dimensions of the matrix m are incorrectly defined. The dimensions should be [n+1][c+1] instead of [n][c]. This is because you're considering 0 to n coins and 0 to c cost, inclusive.
3. The initialization for m[0][j]=9999; should start from j=0 and not j=1. This is because even for cost 0, you need 0 coins.

Let's correct these issues:

#include<stdio.h>

int min(int a , int b) {
    if(a <= b) {
        return a;
    } else {
        return b;
    }
}

void making_change(int n, int c, int value[]) {
    int i, j;
    int m[n+1][c+1];
    
    for(j=0; j<=c; j++) {
        m[0][j]=9999;
    }
    m[0][0] = 0;
    
    for(i=1; i<=n; i++) {
        m[i][0]=0;
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= c; j++) {
            if (j-value[i-1] < 0) {
                m[i][j] = m[i-1][j];
            } else {
                m[i][j] = min(m[i-1][j], 1+m[i][j-value[i-1]]);
            }
        }
    }
    printf("The number of required coins are : %d", m[n][c]);
}

void main() {
    int i, c, n;
    printf("Enter the number of different coins : ");
    scanf("%d", &n);
    int value[n];
    printf("Enter the total cost : ");
    scanf("%d", &c);
    printf("********************Enter the values of different coins******************** \n");
    for(i=0; i<n; i++) {
        printf("Enter the value of coin %d : ", i+1);
        scanf("%d", &value[i]);
    }
    making_change(n, c, value);
}

Now, this code should give you the correct output for the given input.

---