贪心算法的基本思路

1. 贪心算法的基本思路

2. 贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。
3.2.2.1 贪心算法1
第一步:设置一个记录三角剖分中边的数组T。
第二步:计算点集S中所有点对之间的距离d(pi，pj)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d1，d2，…，dn(n-1)/2，相应的线段记为e1，e2，…，en(n-1)/2，将这些线段存储在数组E中。
第三步:从线段集E中取出长度最短的边e1存到T中作为三角剖分的第一条边，此时k=1。
第四步:依次从E中取出长度最短的边ek，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除ek。这一步运行到S中没有边为止，即至k=n(n-1)/2。
第五步:输出T。
该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n2lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为
1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n3)
在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n3)。
3.2.2.2 贪心算法2
第一步:求点集的凸壳，设凸壳顶点为p1，p2，…，pm，凸壳的边为e1，e2，…，em。并将凸壳顶点按顺序连接成边的ei加入T(三角剖分的边集合)，并且ei的权值被赋为1。凸壳内点的集合为S1={pm+1，pm+2，…，pn}。
第二步:从内部点S1中任取一点pi，求与pi距离最近的点pj，将线段 存入T。
第三步:求与pj距离最近的点(除点pi外)，设为pk，并将线段 存入T，pipjpk构成一个三角形，并将三条边wij、wjk和wki的权值设为1。
第四步:分别求与pi、pj和pk距离最近的点(除点pi、pj和pk本身外)，设为p'i，p'j，p'k，将 加入T，并将这些边的权值设为1，而wij、wjk和wki的值加1，即为2。边的权值为2则表示该边为两个三角形共有。
第五步:对权值为1的边(除e1，e2，…，em外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1。
第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e1，e2，…，em外)。
贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求pk要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为
O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n2)

3. 贪心算法

在某一个标准下，优先考虑做满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。
   即，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
   局部最优   -?->   整体最优
  
 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面是一个个具体 的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。 返回这个最多的宣讲场次。
  
 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金 条，不管切成长度多大的两半，都要花费20个铜板。
   一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。 金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20， 花费30；一共花费90铜板。
   输入一个数组，返回分割的最小代价。
  
 输入：
   正数数组costs
   正数数组profits
   正数k
   正数m
   含义： costs[i]表示i号项目的花费
   profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
   k表示你只能串行的最多做k个项目
   m表示你初始的资金
   说明：
   你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
   输出： 你最后获得的最大钱数。

4. 贪心算法及其应用

求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。
  
 比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装100KG重量的袋子，怎么装才能使得袋子中的豆子价值最大？
  
 我们首先看看这个问题是否符合贪心算法的使用场景？限制值是袋子100KG，期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法，每一个步骤都寻找当下的最优解，怎么做呢？
  
 把仓库里面的每种豆子价值除以重量，得出每种豆子的单价，那么当下的最优解，肯定是尽可能最多地装单价最贵的，也就是先把20KG的黄豆都装上，然后再把30KG的绿豆都装上，再装50KG的红豆，那么此时正好装满袋子，总价值将是270元，这就是通过贪心算法求解的答案。
  
 贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证，我们不用那样，只要心里举几个例子，验证下是否比它更好即可，如果举不出例子，那么就可以认为这就是最优解了。
  
 虽然贪心算法虽然在大部分实践场景中都能得到最优解，但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径，那么答案肯定就是S->A->E->T，总代价为1+4+4=9；
                                          
 然而，实际上的最短路径是S->B->D->T，总代价为6。
  
 所以，不能所有这类问题都迷信贪心算法的求解，但其作为一种算法指导思想，还是很值得学习的。
  
 除了以上袋子装豆子的问题之外，还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题，即找到问题的限制值和期望值。
  
 我们有m个糖果要分给n个孩子，n大于m，注定有的孩子不能分到糖果。其中，每个糖果的大小都不同，分别为S1,S2,S3...,Sm，每个孩子对糖果的需求也是不同的，为N1,N2,N3...,Nn，那么我们如何分糖果，才能尽可能满足最多数量孩子的需求？
  
 这个问题中，限制值是糖果的数量m，期望值满足最多的孩子需求。对于每个孩子，能用小的糖果满足其需求，就不要用大的，避免浪费。所以我们可以给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。
  
 我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张，现在要购买一个价值K元的东西，请问怎么才能适用最少的纸币？
  
 这个问题应该不难，限制值是各个纸币的张数，期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱，当再加一张100元就超过K时，就更换小面额的，直至正好为K元。
  
 对于n个区间[L1,R1],[L2,R2]...[Ln,Rn]，我们怎么从中选出尽可能多的区间，使它们不相交？
  
 我们需要把这个问题转换为符合贪心算法特点的问题，假设这么多区间的最左端点是Lmin，最右端点是Rmax，那么问题就是在[Lmin,Rmax]中，选择尽可能多的区间往里面塞，并且保证它们不相交。这里，限制值就是区间[Lmin,Rmax]，期望值就是尽可能多的区间。
  
 我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。
  
 贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。

5. 贪心算法的介绍

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

6. 贪心算法的特性

7. 贪心算法是什么

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

比如最小生成树Kruskal算法，每次在不构成环的前提下，总是选择权最小的边。

8. 什么是贪心算法？

贪心算法的基本思想就是分级处理。
贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。

贪心算法可解决的问题通常大部分都有如下的特性：
1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
5、最后，目标函数给出解的值。