贪心算法的证明题

贪心算法的证明一般是比动态规划要复杂。
原因是贪心算法的证明有两个，一个是最优子结构，另外一个是贪心选择性质。
贪心选择性质： 可以通过局部最优选择来构造全局最优解
证明：一般考虑某个子问题的最优解，然后考虑用一个贪心选择替换其中某个选择，修改此解，导出更小子问题。
最优子结构同动态规划，而且其实一般也不是特别需要证明，关键还是在证明问题具有贪心选择性质，下面是尝试证明。

1.活动选择问题

贪心选择性质的证明：假设一个子问题是Si，其一个最优解为Ai，（考虑一个子问题的最优解），我们选择子问题中最高结束的活动am（贪心选择），假设Ai中最早结束的活动我ae，如果ae=am，显然am在Ai中，如果ae>am,如果用am代替ae所得Ai’也还是最优解（代替），所以该子问题最优解可以表示为am+Si’最优解（拆分）。
大概证明步骤如下：子问题最优解，贪心选择，代替，拆分。

最优子结构的证明:假设Aij是活动i到j（不含j）的最优解，若Aij中包含ak，则可以将其划分为Aik+ak+Akj，反证法证明Aik、Akj都是最优解即可。

2.分数背包问题

贪心选择性质的证明：不妨假设p1/w1>=p2/w2>=…>=pn/wn
则按照贪心选择的最优解是X（x1，x2,…xn）,如果全为1，显然是最优解，如果不全为则假设在j处最先不为，可知前面全为1，后面全为0，xj在两者之间。
又假设Y（…）为理想最优解，设两者的序号最小在k处有xk！=yk，显然xk>yk(k>j,超重，k=j，要么Y是X，要么后面还有得证，k<j,xk=1,显然得证 )
然后假设有xk代替yk，构造Z，证明效应更高，用Z代替Y，如此反复直到Z=X。
这个证明也是一步步局部构造得到最优解的过程。按照先前的步骤xk是贪心选择，构造Z为代替。

3.Huffman编码

注意最后得到的树一定是一棵满二叉树。
贪心选择性质的证明：

这里的证明用构造法，用x，y代替a，b位置。

反证法

（注，这里两个引理的1证明特别是第二个我不太熟悉，日后再补充吧）