Coin Change: Minimum number of coins

Problem:

You are given n types of coin denominations of values v(1)<v(2)<...<v(n) (all integers). Assume v(1)=1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible.


#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,n,den[20],temp[20],min,min_idx, S, numcoins = 0;
    printf("Coin Change with min no. of coins\nEnter the total change you want: ");
    scanf("%d",&S);
    printf("Enter the no. of different denominations of coins available: ");
    scanf("%d",&n);
    printf("Enter the different denominations in ascending order: \n");
    for(i=0;i<n;i++)
        scanf("%d",&den[i]);
    while(S>0)
    {
        for(i=0;i<n;i++)
        temp[i] = S / den[i] ;
        /*calculate min from temp */
        min = temp[0] ;
        for(i=0;i<n;i++)
        {
            if(min > temp[i] && temp[i]!=0)
            {
                min = temp[i] ;
                min_idx = i ;
            }
        }
        numcoins += min ;
        S -= den[min_idx] * min ;
    }
    printf("min no of coins = %d" , numcoins) ;
    return 0;
}

In several solutions on the internet, I saw code using an array of the size of the total sum or value S, whereas I use only 2 arrays of size n, the number of different denominations available. That's why I was wondering whether my approach is correct or whether it's flawed.

Is it better or worse in terms of time complexity? Also, am I properly using dynamic programming principles in my code? Can it be made more efficient? The code ran correctly for several test cases.

I am sorry for poor code formatting and a not-so-clean code. It is a small code, so I hope it is understandable. My main concern is whether the code is dp or not, and if it can be improved for efficiency.

Answer

Bug

You code is currently too simplistic. All it does is make change from the highest denomination possible. It fails on the following input:

 Enter the total change you want: 6
 Enter the no. of different denominations of coins available: 3
 Enter the different denominations in ascending order:
 1 3 4
 min no of coins = 3

Your program thought the change should be: 4 1 1 but the best solution was actually 3 3.

Your program doesn't currently use any dynamic programming principles. In order to do so, you would need to keep an array holding the best number of coins per change amount. You could then iterate starting at 1 and build up to the total change requested.

Attribution
Source : Link , Question Author : CyberLingo , Answer Author : Community

Leave a Comment