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, denomwill be {10,7,1}，它将选择 1 个demon[1]。