【计算机算法设计与分析】最优子结构和贪心选择性质的证明

最优子结构性质（反证法）

• 计算某问题的最优解包含的计算该问题的子问题也是最优解。事实上，如果找到子问题的更优解，则可以替换当前子问题的解，得到一个比最优解更优的解，这是一个矛盾。

贪心选择性质（数学归纳法）

• 先设一个最优解(为所给定的总元素集合，且和均按照某种有利于算法贪心进行的顺序进行排序)，并且设为最优解的第一个元素(即)。
• 1）当时，就是一个以贪心选择开始的最优解；
• 2）当时，设，由于的价值与的价值相等(即能做到的也可以做到)，且是最优的，故也是最优的，因此是以贪心选择元素1开始的最优解。