安徽集团网站建设,社区微网站建设需求分析,襄阳网站建设价格低,西部数码域名注册官网下面的内容主要参考了数据结构与算法之美。
贪心算法的应用有#xff1a; 霍夫曼编码#xff08;Huffman Coding#xff09; Prim和Kruskal最小生成树算法 01背包问题(当允许取部分物品的时候) 分糖果 我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃#xff…下面的内容主要参考了数据结构与算法之美。
贪心算法的应用有 霍夫曼编码Huffman Coding Prim和Kruskal最小生成树算法 01背包问题(当允许取部分物品的时候) 分糖果 我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃但是糖果少孩子多mn所以糖果只能分配给一部分孩子。每个糖果的大小不等这m个糖果的大小分别是s1s2s3……sm。除此之外每个孩子对糖果大小的需求也是不一样的只有糖果的大小大于等于孩子的对糖果大小的需求的时候孩子才得到满足。假设这n个孩子对糖果大小的需求分别是g1g2g3……gn。 如何分配糖果能尽可能满足最多数量的孩子 我们可以把这个问题抽象成从n个孩子中抽取一部分孩子分配糖果让满足的孩子的个数期望值是最大的。这个问题的限制值就是糖果个数m。 我们现在来看看如何用贪心算法来解决。对于一个孩子来说如果小的糖果可以满足我们就没必要用更大的糖果这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面对糖果大小需求小的孩子更容易被满足所以我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子对我们期望值的贡献是一样的。 我们每次从剩下的孩子中找出对糖果大小需求最小的然后发给他剩下的糖果中能满足他的最小的糖果这样得到的分配方案也就是满足的孩子个数最多的方案。 假设我们有n个区间区间的起始端点和结束端点分别是[l1, r1][l2, r2][l3, r3]……[ln, rn]。我们从这n个区间中选出一部分区间这部分区间满足两两不相 交端点相交的情况不算相交最多能选出多少个区间呢 这个问题的解决思路是这样的我们假设这n个区间中最左端点是lmin最右端点是rmax。这个问题就相当于我们选择几个不相交的区间从左到右将[lmin,rmax]覆盖上。我们按照起始端点从小到大的顺序对这n个区间排序。 我们每次选择的时候左端点跟前面的已经覆盖的区间不重合的右端点又尽量小的这样可以让剩下的未覆盖区间尽可能的大就可以放置更多的区间。这实 际上就是一种贪心的选择方法。 在一个非负整数 a 中我们希望从中移除 k 个数字让剩下的数字值最小如何选择移除哪 k 个数字呢 由最高位开始比较低一位数字如高位大移除若高位小则向右移一位继续比较两个数字直到高位大于低位则移除循环k次如 4556847594546移除5位-》455647594546-》45547594546-》4547594546-》4447594546-》444594546 假设有 n 个人等待被服务但是窗口只有一个每个需要被服务的时间长度是不同的如何安排被服务的先后顺序才能让这 n 个人总的等待时间最短 由等待时间最短的开始服务
注意Dijkstra不是贪心算法事实上它是动态规划算法求得的解全局最优解
