Question

I'm trying to find a straight forward answer to a simple problem.. Here it is..

say you have a coin change algorithm with n=10 in the system of denomination of d(1) = 1, d(2) = 7, and d(3) = 10.

now given this implementation of the algorithm from a textbook..

Greedy_coin_change(denom, A)
{
    i = 1;
    While (A > 0) {
        c = A/denom[i];
print(“use “+c+”coins of denomination”+denom[i];
        A = A – C * denom[i];
        i = i+1;
    }
}

wouldn't the result be: "use 10 coins of denomination 1" ?

This is because of course, from my understanding, denom[1] = 1, denom[2] = 7, denom[3] = 10. Correct?

If this is the case, the algorithm would not be considered optimal, correct?

However, there is one small statement above the code that I'm not sure if it should even be taken as part of the code, here it is:

denom[1] > denom[2] > ... > denom[n] = 1.

Was it helpful?

Solution

denom[1] > denom[2] > ... > denom[n] = 1.

Means that the items in the input should be ordered from largest to smallest.

Take it as a precondition for the algorithm (i.e. this is necessary for the algorithm to work).

Thus, if given 1,7,10, denom will be {10,7,1} and it will pick 1 of demon[1].

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top