第10次课贪心

活动选择问题：

![image-20200604174911323](.第10次课贪心_images/image-20200604174911323.png)

部分子问题的解就可以得出原问题的解，这时用动态规划，效率比较低。

贪心法解此问题：【25：00】

![image-20200604175919351](.第10次课贪心_images/image-20200604175919351.png)

![image-20200604180940273](.第10次课贪心_images/image-20200604180940273.png)

【55：00】

![image-20200604193321831](.第10次课贪心_images/image-20200604193321831.png)

![image-20200604202850019](.第10次课贪心_images/image-20200604202850019.png)

【01：20：00】

![image-20200604202923018](.第10次课贪心_images/image-20200604202923018.png)

最优子结构性质也是贪心方法的必要条件。

动态规划中是把所有子问题的解算出来，做比较。

贪心选择和贪心选择性质（贪心选择的正确性）是不一样的。

【01：30：00】

![image-20200604203705822](.第10次课贪心_images/image-20200604203705822.png)

局部最优+ 贪心选择 =》全局最优

局部最优是指只有1个子问题。

【01：37：00】

![image-20200604204050460](.第10次课贪心_images/image-20200604204050460.png)

【01：45：00】

![image-20200604204740393](.第10次课贪心_images/image-20200604204740393.png)

![image-20200604205418797](.第10次课贪心_images/image-20200604205418797.png)

【-2 03：00】

![image-20200604210139574](.第10次课贪心_images/image-20200604210139574.png)

满是指除了叶子结点，每个结点都有2个孩子

![image-20200604210914290](.第10次课贪心_images/image-20200604210914290.png)

Q是优先权队列（二叉堆）。

extract-min从堆中弹出1个。

【15：40】

![image-20200604211203516](.第10次课贪心_images/image-20200604211203516.png)

![image-20200604211534116](.第10次课贪心_images/image-20200604211534116.png)

算法导论笔记

ustc 算法导论笔记

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

第10次课 贪心