문제

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.

도움이 되었습니까?

해결책

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].

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top