贪心算法的证明过程,是不是只有先证明了贪心选择性质之后,再以贪心选择为前提证明其最优子结构?换句话说,如果不证明其贪心选择性质,其最优子结构性质也就无从谈起?或者即使能证明最

　　贪心算法的证明过程,是不是只有先证明了贪心选择性质之后,再以贪心选择为前提证明其最优子结构?

　　换句话说,如果不证明其贪心选择性质,其最优子结构性质也就无从谈起?或者即使能证明最优子结构性质（比如动态规划中的最优子结构）,但也不能保证是贪心选择需要的最优子结构?

　　附：我个人对活动安排问题的最优子结构性质的证明,求修正!

　　证明：设首次贪心选择的活动及其重叠活动集合为A,剩余活动集合为B,最优解活动个数为m,若子问题B的最优解不为m-1；（此证明的前提是贪心选择性质已证明）

　　1）若B最优解个数大于m-1,则A集合贪心选择的活动1与B集合的最优解活动兼容,组成一个新的最优解,则最优解个数大于m,与最优解解个数为m矛盾,假设不成立；

　　2）若B最优解个数小于m-1,由于A中贪心选择已确定选择活动1,则A中其他活动与活动1不相容必然不能选,如果整体最优解结合C为{z1,z2,z3,.zm},则次解中必然包含活动1,不然不包含与1不兼容的活动,则总的活动中剩下的活动显然就是集合B,则最优解集合C去除活动1之后的其他元素必然组成的是活动集合B的最优解集合,设为集合D,则集合C可表示为{活动1,D},由于由假设集合B的最优解集合小于m-1,则整体最优解集合C个数小于m,与前提整体最优解活动个数为m矛盾,假设不成立.

　　综上,活动安排问题最优子结构可更形象描述为贪心选择问题的最优解为每次贪心选择的活动及其重叠活动与剩余活动这两个子活动集合问题的最优解的和.

　　我理解错了,最优子结构是可以独立证明的.有知道怎样用数学归纳法证明出活动安排问题整体最优解的没?请高手简要写下证明过程.