问题标题: 酷町堂：预习

一、课堂内容

1. 贪心算法的基本思想

    在对一个问题求解时，总是做出在当前看来是最好的选择。也就是说，把一个较复杂的问题分解成若干子问题，对于每个子问题来说， 不从整体最优上加以考虑，只做出在某种意义上的局部最优解。
    通过每次得到局部最优解答，逐步推导出问题，进而得到全局最优解。

    通俗地来讲，就是怎么做有利就怎么做。

贪心问题的解决总是伴随着排序，我们以选择尽量优的解的原则，将事物按照最优的解在最前的顺序排好，然后依次选取最优选择，构成整体最优解。
 

2. 容量相关的贪心问题

       想象这样一个场景，有天你流落到了一个荒岛上，你带着一个容量固定的空背包，在荒岛上你发现了几小堆金砂，恰好你能分辨这些金砂的价值。这时有艘船来了，船不会在荒岛上停留，你登上船就不能下来了，所以你只能带走一个背包的金砂，不可能重新回来装。这时你会怎么装这些金砂呢？
       此时可以采取的贪心策略是：先取价值最高的一堆金砂，价值最高的这堆取完了再取价值第二高的一堆金砂，如果价值第二高的金砂也取完了再取价值第三高的，…… ，直到装满背包。

给定一个容量固定的背包，然后由一堆价值不同的东西可供选择（这些东西可以以任意体积装进背包），怎么选取才能使背包装满时获得的价值最大？
采取的策略就是先选取价值高的，选完了再选次高的，……，直到装满背包。