贪心算法的基础知识
01基本概念
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
02贪心算法的基本思路
解题的一般步骤是：
1.建立数学模型来描述问题； 2.把求解的问题分成若干个子问题； 3.对每一子问题求解，得到子问题的局部最优解； 4.把子问题的局部最优解合成原来问题的一个解。
03该算法存在的问题
不能保证求得的最后解是最佳的
不能用来求最大值或最小值的问题
只能求满足某些约束条件的可行解的范围
04贪心算法适用的问题 贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。
05贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
06贪心算法的实现框架 从问题的某一初始解出发：
while (朝给定总目标前进一步){ 利用可行的决策，求出可行解的一个解元素。} 由所有解元素组合成问题的一个可行解；
07例题分析
如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。 话不多说，我们来看几个具体的例子慢慢理解它：1.活动选择问题这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合s，其中各项活动按照结束时间单调递增排序。 考虑使用贪心算法的解法。为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。 如果我们每次都选择开始时间最早的活动，不能得到最优解： 如果我们每次都选择持续时间最短的活动，不能得到最优解： 可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。 #include#include#includeusing namespace std; int n;struct act{ int start; int end;}act[100010];bool cmp(act a,act b) { return a.end0) num=-1; return num;}int main(){ int money; cin>>money; int res=solve(money); if(res!=-1) cout<>n>>m; for(int i=0;i>speed[i]; sort(speed,speed+n,cmp); for(int i=0;i(*(point *)b).x?1:-1;}int main(){ int n,d; int num=1; while(cin>>n>>d) { int counting=1; if(n==0&&d==0) break; for(int i=0;i>x>>y; if(y>d) { counting=-1; } double t=sqrt(d*d-y*y); //转化为最少区间的问题 point[i].x=x-t; //区间左端点 point[i].y=x+t; //区间右端点 } if(counting!=-1) { qsort(point,n,sizeof(point[0]),cmp); //按区间左端点排序 double s=point[0].y; //区间右端点 for(int i=1;is) //如果两个区间没有重合,增加雷达数目并更新右端点 { counting++; s=point[i].y; } else if(point[i].yt; while(t--) { cin>>n; priority_queue q; res=0; for(int i=1;i>price[i]; } res-=price[1]; res+=price[n]; for(int i=2;iq.top()) { res=res-2*q.top()+buy+sell; q.pop(); q.push(buy); q.push(sell); } else { res=res-buy+sell; q.push(sell); } } else { res=res-buy+sell; q.push(sell); } } cout< 对每一个字符规定一个01串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。可能无前缀码是一个更好的名字，但是前缀码是一致认可的标准术语。编码的前缀性质可以使译码非常简单：例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。译码过程需要方便的取出编码的前缀，为此可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标。
从上图可以看出，最优前缀编码码的二叉树总是一棵完全二叉树，而定长编码的二叉树不是一棵完全二叉树。给定编码字符集c及频率分布f，c的一个前缀码编码方案对应于一棵二叉树t。字符c在树t中的深度记为dt(c)，dt(c)也是字符c的前缀码长。则平均码长定义为：
使平均码长达到最小的前缀码编码方案称为c的最优前缀码。 huffman编码的构造方法：先合并最小频率的2个字符对应的子树，计算合并后的子树的频率；重新排序各个子树；对上述排序后的子树序列进行合并；重复上述过程，将全部结点合并成1棵完整的二叉树；对二叉树中的边赋予0、1，得到各字符的变长编码。
蓝牙耳机什么牌子好，哪个蓝牙耳机性价比最高
长三角地区氢能产业园区
高速低功耗CMOS图像传感芯片
300元有什么好用的蓝牙耳机？300左右无线蓝牙耳机推荐
PHY芯片上电时序要求和问题分析
贪心算法的基础知识
Intel宣布正式退役KabyLake处理器
蓄电池容量放电测试仪的技术参数
什么是压电薄膜？ATA-7050高压放大器如何驱动压电薄膜传感器？
魅蓝Note6上市爆卖，自家旗舰魅族pro7被“气晕”，暴降6百求关注
骆驼AGM启停电池受推崇
华为荣耀V9评测：2K屏幕+双摄 3499价位霸主
2019年3D打印的五种趋势分析
电路原理图七个小技巧
【汽车与环境创新论坛】探讨汽车轻量化关键技术与挑战
浅析微机线路保护装置
联动控制台是什么,有哪些优点
基于物联网的设备如何帮助城市变得更智能
机器人产业正在与新兴技术不断的融合
台积电或与三星联手建立本土芯片制造工厂
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
02贪心算法的基本思路
解题的一般步骤是：
1.建立数学模型来描述问题； 2.把求解的问题分成若干个子问题； 3.对每一子问题求解，得到子问题的局部最优解； 4.把子问题的局部最优解合成原来问题的一个解。
03该算法存在的问题
不能保证求得的最后解是最佳的
不能用来求最大值或最小值的问题
只能求满足某些约束条件的可行解的范围
04贪心算法适用的问题 贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。
05贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
06贪心算法的实现框架 从问题的某一初始解出发：
while (朝给定总目标前进一步){ 利用可行的决策，求出可行解的一个解元素。} 由所有解元素组合成问题的一个可行解；
07例题分析
如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。 话不多说，我们来看几个具体的例子慢慢理解它：1.活动选择问题这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合s，其中各项活动按照结束时间单调递增排序。 考虑使用贪心算法的解法。为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。 如果我们每次都选择开始时间最早的活动，不能得到最优解： 如果我们每次都选择持续时间最短的活动，不能得到最优解： 可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。 #include#include#includeusing namespace std; int n;struct act{ int start; int end;}act[100010];bool cmp(act a,act b) { return a.end
从上图可以看出，最优前缀编码码的二叉树总是一棵完全二叉树，而定长编码的二叉树不是一棵完全二叉树。给定编码字符集c及频率分布f，c的一个前缀码编码方案对应于一棵二叉树t。字符c在树t中的深度记为dt(c)，dt(c)也是字符c的前缀码长。则平均码长定义为：
使平均码长达到最小的前缀码编码方案称为c的最优前缀码。 huffman编码的构造方法：先合并最小频率的2个字符对应的子树，计算合并后的子树的频率；重新排序各个子树；对上述排序后的子树序列进行合并；重复上述过程，将全部结点合并成1棵完整的二叉树；对二叉树中的边赋予0、1，得到各字符的变长编码。
蓝牙耳机什么牌子好，哪个蓝牙耳机性价比最高
长三角地区氢能产业园区
高速低功耗CMOS图像传感芯片
300元有什么好用的蓝牙耳机？300左右无线蓝牙耳机推荐
PHY芯片上电时序要求和问题分析
贪心算法的基础知识
Intel宣布正式退役KabyLake处理器
蓄电池容量放电测试仪的技术参数
什么是压电薄膜？ATA-7050高压放大器如何驱动压电薄膜传感器？
魅蓝Note6上市爆卖，自家旗舰魅族pro7被“气晕”，暴降6百求关注
骆驼AGM启停电池受推崇
华为荣耀V9评测：2K屏幕+双摄 3499价位霸主
2019年3D打印的五种趋势分析
电路原理图七个小技巧
【汽车与环境创新论坛】探讨汽车轻量化关键技术与挑战
浅析微机线路保护装置
联动控制台是什么,有哪些优点
基于物联网的设备如何帮助城市变得更智能
机器人产业正在与新兴技术不断的融合
台积电或与三星联手建立本土芯片制造工厂