《贪心算法贪心算法》由会员分享，可在线阅读，更多相关《贪心算法贪心算法（72页珍藏版）》请在金锄头文库上搜索。
1、贪心算法,顾名思义，贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。,贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,活动安排问题,设有n个活动的集合s=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。 si, fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si= fj或者sj= fi,怎样对这n个活动进行安排才能
2、令最多的活动可以使用资源？,活动安排问题也就是要在所给的活动集合中选出最大的相容活动子集合,思路：按照结束时间递增序列将活动排序，使得f1=f2=fn 满足相容关系后，按照标号从小到大选择活动 注意：排序，贪心选择,活动安排问题的贪心策略：使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。,template void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,各活动的起始时间和结束时间存储于数组s和f中且按
3、结束时间的非减序排列,活动安排问题的贪心算法,算法GreedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法GreedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。,贪心算法的基本要素,最优子结构性质 贪心选择性质,最优子结构性质,一个问题的最优解包含了它子问题的最优解。 举例： 你从北京经过广州到海南的最短距离，肯定包括北京到广州的最
4、短距离，以及广州到海南的最短距离,贪心选择性质,所求问题的最优解，可以通过一系列的局部最优解的选择，即贪心选择得到 在当前状态下做出局部最优，然后解这个选择时候产生的子问题 从全局看来，运用贪心策略解决的问题在程序的运行过程中无回溯过程,给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,背包问题,用贪心算法解背包问题的基本步骤,首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包
5、。 若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去，直到背包装满为止。,void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; ,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。,0-1背包问题,给定n种物品和一个背包。物品i的重量是Wi，其价值为
6、Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。,特殊的0-1背包问题,在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。,对于01背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的01背包问题，则可以用贪
7、心算法去解。 首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。 这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。,最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,算法描述,最优装载问题可用贪心算法求解 贪心选择策略:重量最轻者先装 可产生最优装载问题的最优解,template void Loading(int x, Type w, Type c, int n) int
8、 *t = new int n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n ,贪心选择性质,可以证明最优装载问题具有贪心选择性质。 k = mini|xi=1 1=1,最优子结构性质,最优装载问题具有最优子结构性质。,算法Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。,贪心算法的基本步骤,从问题的某个初始解出发 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模 将所有部分解综合起来，得
9、到问题的最终解,汽车加油问题,一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n和k(k = 1000)个加油站位置，编程计算最少加油次数。,7 7 1 2 3 4 5 1 6 6 5 1 50 5 0 0 4 No Solution,旅行规划问题,G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。 出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规
10、划才能使旅行的费用最省。,编程任务： 对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。,Sample input 275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2 Sample output 26.95 ci0=220.0/27.4=8.029 ci1=0 ci2=(275.6-220)/27.4=2.029 Total = 8.029*2.8 + 2.029*2.2 = 26.95,第一步：判断旅行家能否到达目的地 假设在任一个加油站都加满油，能否到达终点,
11、第二步：预算最少费用 采用贪心算法的思想求解,汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。 如果以p(i)表示第i油站的汽油价格，x(i)表示在第i油站所加汽油的量，总费用为 P p(i) * x(i) i=0,1,.,n,两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油总量（即x(i) i=0,1,.,n ）自然也是固定不变的。 根据使费用最少的求解目标，要使费用函数取得最优值（在此为最小值），必须使p(i)尽可能小：也就是汽车要尽可能在价格便宜的油站加油。,汽车每到达一个油站i（包括出发点第0站，但不包括目的地第n+1站），都要检查是否需要加
12、油。,如果汽车在某个油站i需要加油，那么，就先将该油站的汽油价格p(i)与下一油站的汽油价格p(i+1)进行比较，若p(i)=p(i+1)，加油时，只需保证油箱中的汽油能够到达下一油站（第i+1站）即可； 否则，继续将p(i)与第i+2站的汽油价格p(i+2)进行比较，,判断是否需要在第i站加油的条件可以确定为：在到达第i站时，汽车油箱中的剩余汽油（用变量rest表示剩余汽油的多少）是否足够行驶到下一更便宜的油站j，即rest*e是否大于或等于d(j)-d(i)。 如果一直找不到比第i个油站更便宜的油站j，则在第i个油站加满油（如果不用加满就已经到了终点，则加油量应该满足刚好到达终点）,哈夫曼
13、编码,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。,前缀码,对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。,编码的前缀性质可以使译码方法非常简单 平均码长定义为： 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 表示最优前缀码的二叉树树中任一结点都有2个儿子结点,构造哈夫曼编码,哈夫曼提出构造最优前缀码
14、的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。,算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。 一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。 经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。,算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于
15、最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。,选址问题,给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值 表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。 试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一 个算法求解上述问题。,单源最短路径,给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点v，称为源。现在要计算从源到所有其它各顶点的最短路
16、长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。,单源最短路径,Dijkstra算法是解决单源最短路径问题的贪心算法。 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。,通过分步方法求出最短路径,每一步产生一个到达新的目的顶点的最短路径 下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点,单源最短路径,初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度 Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记
