Programming

Hello,

I was reading Heuritics text and came across an algorithm below. Finding hard to analyze it can any one help me out below...

How to analyze if I take say no. of types are 5 and each type has say 20 coins.

thanks.

Code:

Let {c1, c2...cn=1} be a set of distinct coin types where ci is an integer.
Sort coin types in decreasing order.
    numOfCoin = 0;
    amountRemain = M;
    for (i=1; i<=n && amountRemain>0; ++i) {
        j = amountRemain/ci;
        numCoin += j;
        amountRemain -= j*ci;
    }
    output numCoin;

For example, start with amountRemain=65, C1=25, C2=5.

First loop:
j = (65/C1) = (65/25) = 2 # Ignore the fraction
numcoin += j = (0 + j) = (0 + 2) = 2
amountRemain -= (j * C1) = 65 - (2*50) = 15

i.e. two coins of value 25.

Next loop:
j = (15 / C2) = (15 / 5) = 3
numCoin += 3 = (2 + 3) = 5
amountRemain -= (j * C2) = 15 - (3*5) = 0

Now, amountRemain is 0, so no more coins are needed.

In this method, it has calculated that, to pay 65 cents in quarters and nickels should take 2 quarters and 3 nickels, for a total of 5 coins.