質問

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