任何贪心算法必须有数学上的正确性证明.虽然最优分解问题有很多算法介绍,但是没有看到算法的正确性证明.本文用数学归纳法给出最优分解问题贪心算法的正确性证明.同时,最优分解问题也是一个贪心选择性质和最优子结构性质不能独立证明的很好的例子.
科研之友
微信
新浪微博
Facebook
分享链接
