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 
#include 

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;i0)
    {
        for(i=0;i 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.

Currently, your code is next to unreadable.

The variable names are too cryptic. Names like den and S don't tell anything about the context of the variable.

Please, use descriptive names.

You don't give space for your variables to breath. You crammed everything up and that makes it harder to read.

An example:

for(i=0;i<n;i++)
temp[i] = S / den[i] ;

Could be written as

for(i = 0; i < n; i++)
temp[i] = S / den[i];

Still on the same for, you forgot to indent it.

Indentation is important to check what belongs where. Code is read far more times than written. Improve it's readability.

Still beating on that same for, you should always have brackets around your statements. Remember the Apple SSL bug? Well, it may happen with you.

Try this instead:

for(i = 0; i < n; i++)
{
    temp[i] = S / den[i];
}

You should declare your variables as close as possible of when you will use them.

One example is this:

for(i = 0; i < n; i++)
{
    temp[i] = S / den[i];
}

I would do like this:

for(int i = 0; i < n; i++)
{
    temp[i] = S / den[i];
}

A few lines below, you have this:

min = temp[0] ;
for(i=0;i<n;i++)

You start by giving min the value of temp[0]. Why don't you start the loop at 1? You reduce 1 iteration!

Like this:

int min = temp[0];
for(int i = 1; i < n; i++)

This would speed-up your code by a very small bit, but it is important to notice.

And to squeeze a tiny bit of performance, you can change:

if(min > temp[i] && temp[i]!=0)

Into this:

if(temp[i]!=0 && min > temp[i])

Now you ask: Why? And the answer is because of shortcut evaluation. If temp[0] is false, it won't evaluate min > temp[i], because we know that it will be false as well.

This won't save much, but you shave some comparisons. Which is really good!

If you want, I can even eliminate that tiny loop I've refered before:

int min = S / den[0];
int min_idx = 0;
for(int i = 1; i  temp)
    {
        min = temp;
        min_idx = i;
    }
}

And so, you can eliminate the tiny for and the temp[20]. This was untested and may not work!

You trust too much in the user. You have no validation what-so-ever! I could say I have 5 coins and then only give 2 denomination in the wrong order. What would happen?

Also, how can I say that I have a 0.5€ coin? Or a 2€ coin? Would it be 50 and 200?

I'm really sorry if I said something that might not fit at 100%. I'm not 100% confortable with C. But I hope I've helped you.

StackExchange Code Review Q#100830, answer score: 8