【习题解答】 贪心算法设计要素

11.1

算法思想如下： + 把S表示为c进制形式 + 拿枚面值为的硬币,

正确性如下： + 首先该算法输出的硬币，确实刚好能换S金额的钱，这个根据c进制运算即可。 + 假设存在更优的换法，该更优的换法同样可以用c进制串（要求每一位的值都小于c）表示出来。 * 更优的换法之所以可以表示为c进制串（每一位的值都小于c）是因为如果某一位大于等于c，则可以用更高一位的硬币代替（也就是进位操作），这样能得到一个更优的串，直至得到c进制串 * c进制串对同一个大小的数表示是唯一的，这个结论很重要。 * 更优的换法经过若干次优化后变成了我们的换法，矛盾。说明我们的换法就是最优的。