算法201006–贪心1.ppt

活动安排问题 设有n个活动的集合E = {1, 2, …, n}，其中每个活动都要求使用同一资源，且在同一时间里只能有一个活动可以使用该资源。现要求给出一个活动安排，使得利用该资源活动为最多。 每个活动i都有使用该资源的一个启始时间si和一个结束时间fi，si＜fi，其占用资源的时间为半开区间[si , fi)。若区间[si , fi)与区间[sj , fj)不相交，则称活动i与活动j是相容的。 活动安排问题就是求E的最大相容活动子集。 活动安排问题的描述 用数组A分别存放所有活动的启始时间和结束时间以及是否予以安排的标记。 某项活动结束时间愈早，安排其它活动的剩余区间愈大。所以贪心策略为尽量选择结束时间早的活动来安排。 为此，将数组中的活动按结束时间的非减顺序排序，即f1≤f2≤…≤fn。 显然排序需要的时间为O(nlogn)。 活动安排问题的算法 ActionArragement(int n, Type A[][]) //A[i][0], A[i][1], A[i][3]分别为s, f和安排标记 { 将A依照A[i][1]的非减顺序排序； int j = 1; A[j][3] = 1; //先安排活动1 for (int i = 2; i = n; i++) { if A[i][0] = A[j][1] //若活动i与j相容 {A[i][3] = 1; j = i;} // 则安排活动i else A[i][3] = 0 } // 否则不安排活动i } 活动安排问题实例 设待安排的11个活动的始末时间排序如下： 贪心方法的抽象化控制 Procedure GREEDY(A,n) solution?Ф for i?1 to n do x?SELECT(A) if FEASIBLE(solution,x) then solution?UNION(solution,x) endif repeat return (solution) End GREEDY 贪心算法也能获得最优解 设活动集合E={1, 2, …, n}已经按结束时间的非减顺序排列，活动1具有最早结束时间。 首先，必定有一个最优解包含活动1。 贪心方法的数据选择策略(2) 先装入物品3, x3=1, p3x3 =15，再装入重量为10的物品2， ∑pixi =15+24*10/15=31。 0-1背包问题的形式化描述 问题的形式描述是：给定c＞0，wi＞0，vi＞0，1≤i≤n，求n元0-1向量(x1, x2, …, xn)，使得 n ∑wixi≤c且 i=1 n ∑vixi达到最大。即： i=1 n max∑vixi i=1 n ∑wixi≤c i=1 xi∈{0, 1} 1≤i≤n * 第四章 贪心算法 贪心算法的基本思想 背包问题的贪心求解 带有期限的作业排序 最小生成树 最短路径 最优归并模式 哈夫曼编码 贪心算法的基本思想 背包问题的贪心求解 带有期限的作业排序 贪心算法 解与解向量 现实中有这样的问题： 有n个输入和一组约束条件。 解的结构对应为一个n维向量（x1,x2,?,xn）,其中xi（i=1,2,?,n） 对应为输入元素的相应取值（具体根据实际问题不同取值方法不同）。 （x1,x2,?,xn）需满足相应约束条件 满足约束条件的任意一组输入称为问题的一组可行解；使目标函数达到最大或最小（根据实际问题的要求）的可行解称为最优解。贪心法用于求解的问题，其目标往往是求最优解。 例子-1 1 找零钱问题：以人民币1元，2元，5元，10元，20元，50元，以99元为例，要求所找的张数最少 ？ 99=50+20*2+5+2*2 2 古代有一位医师到某个到处都是草药的山洞里采药，山洞里有一些不同的草药，同时每种草药只有一株，采每一株都需要一些时间，每一株都有它自身的价值。只能在一段时间内采药，在这段时间里，医师可以采到一些草药，医师了解每种草药需要的时间及其价值。如果是你，你应该如何采药才可以让采到的草药的总价值最大。 例子-2 其他问题 Go Home Travel Investment Budget [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下