硬币的值为 ci，对于每个 i ≥ 0，对于某个整数常数 c > 1。 例如，如果 c = 3，则您的硬币值为 1 (= 30)、3、9 (= 32)、27、...
您需要设计一种算法，在给定整数值 n 的情况下，使用最少数量的硬币为 n 找零。您可以假设每种面额 ci 的硬币的供应量是无限的，且 ci ≤ n。
我想出了贪婪算法，但我被这个问题困住了：
证明对于任意 i，任何最优解最多有 c − 1 个价值为 ci 的硬币。
我明白了，我明白了它是如何工作的，但我不知道如何用语言表达/展示它。有人可以指出我正确的方向吗？
通常，贪婪算法可以通过以下方式证明是正确的：如果存在（据称）最优解，其结构与您的算法生成的结构不同，您可以将其更改为您的算法将生成的结果，并显示结果一样好或更好。
在这种情况下：假设（为了矛盾起见）存在使用 c 或更多价值 ci 的硬币的最佳解决方案。那么，您如何以贪婪算法的方式改进该解决方案（从而表明以不同方式执行操作的解决方案实际上不是最优的？）