algorithm - 如何解读这个换币算法

Question

我正试图为一个简单的问题找到一个直接的答案..在这里..

假设您在 d(1) = 1、d(2) = 7 和 d(3) = 10 的面额系统中有一个 n=10 的硬币找零算法。

现在从教科书中给出算法的实现..

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;
    }
}

结果不会是:“使用 10 个面额为 1 的硬币”吗？

这当然是因为，根据我的理解，denom[1] = 1，denom[2] = 7，denom[3] = 10。对吗？

如果是这种情况，算法就不会被认为是最优的，对吗？

但是，代码上方有一个小声明，我不确定它是否应该作为代码的一部分，这里是:

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

Answer 1

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

意味着输入中的项目应该从大到小排序。

将其作为算法的前提条件(即这是算法工作所必需的)。

因此，如果给定 1,7,10，denom 将是 {10,7,1} 并且它将选择 1 恶魔[1]。