💡Author：信安2002钱泽枢(ShiQuLiZhi)
🚀欢迎访问我的作业合集：https://sxhthreo.github.io/categories/%E4%BD%9C%E4%B8%9A/
一、题干
假设可换的硬币的单位是 $c$ 的幂，也就是 $c_0, c_1,…,c_k$ ,其中整数 $c>1,k≥1$ 。证明使用贪心算法总可以产生一个最优解。
二、证明
在最优解中，若使用了面值为 $c^i$ 的硬币去找零，则面值为 $c^i$ 的硬币最多只能使用 $c-1$ 个。
设 $k$ 是可换的硬币的种类数，$n$ 是需要找换的总价值，$a_i$ 是使用面值为 $c^i$ 的硬币的数量。
我们将硬币按面值从小到大进行排序。
对于贪心选择，设 $j=max{0\leq i \leq k,c^i \leq n}$，每次我们将会选择面值为 $c^j$ 的硬币，我们的目标是证明贪心解就是最优解，即对于所有的非贪心选择均不是最优解。
对于非贪心选择，我们不会选择面值为 $c^j$ 的硬币，则我们有 $\sum_{i=0}^{j-1} a_{i} c^{i}=n$，其中 $a_i$ 表示使用面值为 $c^i$ 的硬币的个数。若面值为 $c^j$ 的硬币可用，则有 $n\geq c^j$，故 $\sum_{i=0}^{j-1} a_{i} c^{i}\geq c^j$；
又有 $a_i\leq c-1$，则
$\begin{aligned}
\sum_{i=0}^{j-1} a_{i} c^{i} & \leq \sum_{i=0}^{j-1}(c-1) c^{i} \
&=(c-1) \sum_{i=0}^{j-1} c^{i} \
&=(c-1) \frac{c^{j}-1}{c-1} \
&=c^{j}-1 \
&<c^{j}
\end{aligned}$
与 $\sum_{i=0}^{j-1} a_{i} c^{i}\geq c^j$ 矛盾，则非贪心选择不是最优解。故贪心选择是最优解。
