最少硬币支付问题 c的幂次方证明

假设硬币的面值为\(c^0, c^1, ..., c^k\)，其中c是一个大于1的整数，k是一个大于等于1的整数。设\(a_i\)是找n分钱的最优解中面值\(c^i\)的硬币的数量，那么对于\(i=0,1,...,k-1\)，有\(a_i < c\)。这是因为如果\(a_i >= c\)，那么可以用一个面值\(c^{i+1}\)的硬币替换c个面值\(c^i\)的硬币，从而减少了c-1个硬币，这与最优解矛盾。

设j是满足\(c^j <= n\)的最大整数，那么贪心算法会选择至少一个面值\(c^j\)的硬币。如果不选择面值\(c^j\)或更大的硬币，那么设非贪心解使用\(b_i\)个面值\(c^i\)的硬币，对于\(i=0,1,...,j-1\)，那么有\(b_0 * c^0 + b_1 * c^1 + ... + b_{j-1} * c^{j-1} = n\)。由于\(n >= c^j\)，所以上式左边大于等于\(c^j\)。又由于\(b_i < c\)，所以上式左边小于等于\((c-1) * (c^0 + c^1 + ... + c^{j-1}) = (c-1) * (c^j - 1) / (c - 1) = c^j - 1 < c^j\)。这与上面推出的左边大于等于\(c^j\)矛盾。所以不选择面值\(c^j\)或更大的硬币不能产生最优解。

因此，当硬币面值为c的幂次方时，最少硬币支付问题能使用贪心算法.