问题标题: 提前学贪心

J2-v3-阶段3-课时6-贪心算法一：容量问题-课后讲义
一、课堂内容
1. 贪心算法的基本思想
    在对一个问题求解时，总是做出在当前看来是最好的选择。也就是说，把一个较复杂的问题分解成若干子问题，对于每个子问题来说， 不从整体最优上加以考虑，只做出在某种意义上的局部最优解。
    通过每次得到局部最优解答，逐步推导出问题，进而得到全局最优解。

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

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


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

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

J2-v3-阶段3-课时7-贪心算法二：排队问题-课后讲义
贪心算法二：排队问题课后讲义


一、课堂内容
1. 排队等待总时间最少类的问题
    若干个人排队等待，要使得所有人的总等待时间最少，应该让花时间少的人排前面。
    假如5个人排队，第一个人要花3分钟，则所有人都等了3分钟，总共 3* 5=15分钟； 而如果第1个人要花1分钟，则总共只需等1* 5=5分钟。

2. 多窗口排队问题
    如果有多个窗口可以排队，可以想到的一种贪心思路是排队的人看哪个窗口先空出来，就去那个窗口排队。则我们需要始终记录每个窗口排队结束的时间，当有一个新的人来排队时，总是选择排队结束时间最早的那个窗口。
 

贪心算法三：数字的拆分、删除与重组—课后讲义（v3）
一、课堂内容
1. 数字的拆分
将一个大数拆分成小数字的和，如果要求拆分的数量尽量少，则贪心的思路是尽量拆成大的数字，值不够了再往小的数字去拆。

2. 数字删除固定位数
把一个数字删除固定位数，要求最后剩的数字最大，不能只是删除所有小的数字。比如：2131要求删2位，如果是删除两个1，会得到23，但其实删掉21，剩下31才是最大的。
    因为删除后的数字位数是确定的，所以正确的贪心思路应该是让首位数字尽可能大。

2. 数字组合位数
把若干个数字组合成一个新的数字，使其最小。不能够只是把短的数字或者小的数字放前面，比如2和11组合，把11放前面组成的数字更小。
    此时要考虑的是数字组合之后数值更小，比如a和b组合，我们应当比较ab和ba的大小，来确定谁放前面。

贪心算法四：区间问题—课后讲义（v3）
一、课堂内容
1. 区间覆盖类问题
对于区间覆盖类的问题（区间可能有重叠，问被覆盖的区间总大小），
解题时考虑按照每个区间的起点从前往后排序，
然后遍历每个区间，判断当前区间是否与前一个区间相连（判断当前区间的起点在上个区间的终点之前还是之后）。
2. 活动安排问题
限定的场地要安排多个活动，不同的活动间时间可能会冲突，怎么才能安排尽量多的活动？
按照活动的结束时间从小到大排序，尽量安排结束时间早的活动，这样才能为后续安排活动留下更充足的时间。

一、课堂内容
1. 贪心的思路
  对于具体的问题，我们要设计具体的贪心思路，总的来说，就是当前做什么最有利就选择做什么，通过子问题的最优最终可以推得全局的最优解。

2. 建立模型
  对于某些贪心问题，直接想思路并不好想，需要对问题进行分析，建立数学模型，在此基**上确立贪心思路。

3. 验证贪心思路
  对于某个问题贪心思路的正确**验证，我们可以尝试按照此思路是否能举出反例，这是一个很好的筛选贪心思路的方法。

课堂练习代码部分去掉了，有些只有代码的讲义我就没发了