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

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

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

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

• 先设一个最优解$A\subseteq E$($E$为所给定的总元素集合，且$A$和$E$均按照某种有利于算法贪心进行的顺序进行排序)，并且设$k$为最优解的第一个元素(即 k = m i n 1 ≤ i ≤ n { i ∣ x i = 1 } k=min_{1\leq{i}\leq{n}}\{i|x_i=1\} k=min1≤i≤n​{i∣xi​=1})。
• 1）当$k=1$时，$A$就是一个以贪心选择开始的最优解；
• 2）当$k\ge 1$时，设 B = A − { k } ∪ { 1 } B=A-\{k\}\cup\{1\} B=A−{k}∪{1}，由于$A$的价值与$B$的价值相等(即$A$能做到的$B$也可以做到)，且$A$是最优的，故$B$也是最优的，因此$B$是以贪心选择元素1开始的最优解。