2010年8月19日贪心法例题讲解.doc

旅行家的预算(acm) 旅行家的预算 Problem description 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距Di、每升汽油价格 Pi（ il，2，.N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No solution”。Input 输入数据的第一行是四个实数；D1 C D2 P分别表示两个城市之间的距离，汽车油箱的容量，每升汽油能行驶的距离，出发点每升汽油格；第二行是一个整数N,沿途的油站数。第三行到第N+2，每一行是一个油站的基本信息描述，包括该油站离出发点的距离，该油站每升汽油的格。 Output 输出到达目的城市的最小费用(四舍五入到两位小数)，若不能到达目的城市则输出 No solutionSample Input 275.6 11.9 27.4 2.82102.0 2.9220.0 2.2 Sample Output 26.95Problem Source / 测试用例275.6 11.9 17.4 2.82102.0 2.9220.0 2.2142.54/275.6 11.9 10.4 2.83 102.0 2.1160.2 2.3220.0 2.262.99分析：需要考虑如下问题：1） 出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？2） 汽车行程到第几站开始加油，加多少油？可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。对于第一种情况，则油箱需要（d（j）-d（i）/m加仑汽油。对于第二种情况，则需将油箱加满。贪心算法证明如下：设定如下变量：Valuei：第i个加油站的油价；Overi：在第i站时的剩油；Wayi：起点到油站i的距离；XI：X记录问题的最优解，XI记录油站I的实际加油量。首先，X10，Over1=0。假设第I站加的XI一直开到第K站。则有，XI.xk-1都为0，而XK0。 若ValueIValuek，则按贪心方案，第I站应加油为T=（Wayk-WayI）/M-OverI。若TXI, 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用ValueI*W，如果W加仑汽油在油站K加，则须费用ValueK*W，显然ValueK*WValueI*W。 若ValueIValuek，则按贪心规则，须加油为 T=C-OverI（即加满油）。若TXI，则表示在第I站的不加满油，而将一部分油留待第K站加，而ValueIValuek，所以这样费用更高。综合上述分析，可以得出如下算法：I := 1 汽车出发设定为第1个加油站L := C*D2； 油箱装满油能行驶的距离repeat 在L距离以内，向后找第一个油价比I站便宜的加油站J； if J存在 then if I站剩余油能到达J then 计算到达J站的剩油 else 在I站购买油，使汽车恰好能到达J站 else 在I站加满油； I := J； 汽车到达J站until 汽车到达终点；方法一：#includedouble p101,dist101;double c,dic;int N;double cost,rest,need;void init() double box,dd,pp; int k,i; scanf(%lf%lf%lf%lf%d,&box,&c,&dic,&p0,&N); distN+1=box;pN+1=0;dist0=0; for(i=1;i=N;i+) scanf(%lf%lf,&dd,&pp); pi=pp;disti=dd; void wo() int j,k,min1,min2; rest=cost=k=0; while(k=N) j=k;min1=0;min2=0; while(distj+1-distk=c*dic)&(j=N) j+; if(min1=0 & pjpk) min1=j; if(min2=0 | pjpmin2) min2=j; if(j=k) printf(-1n); return ; if(min1!=0) need=(distmin1-distk)/dic-rest; if(need0) need=0; cost+=need*pk; rest=0; k=min1; else need=c-rest; cost+=need*pk; rest=c-(distmin2-distk)/dic; k=min2; int main() init(); wo(); printf(%0.2lfn,cost); 2、 活动安排问题 huodong.pas问题描述 假设有一个需要使用某一资源的n个活动组成的集合S，S=1，n。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei (biei)。若biej或者bjei，则活动i和活动j兼容。你的任务是:选择由互相兼容的活动组成的最大集合（活动最多）。输入格式 输入文件名为：huodong.in，共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间（中间用空格隔开），格式为：n b1 e1 bn en输出格式 输出文件名为：huodong.out，共两行， 第1行可举办活动的个数， 第2行为最大集合中的活动序号，每个数据之间用一个空格隔开。按活动先后输出样例输入 113 51 412 148 120 68 116 105 73 85 92 13样例输出42 8 6 3 活动安排问题一个由需要使用某一资源的n个活动组成的集合S = 1, 2, . , n，该资源一次只能被一个活动占用。每个活动i有个开始时间si和结束时间fi，且si = fi。一旦被选择，活动i就占据半开时间区间si, fi)。如果si, fj)与si, fj)互不重叠，则称活动i和j是兼容的。活动安排问题就是要选择一个由互相兼容的问题组成的最大集合。活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合e=1，2，n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间si，fi内占用资源。若区间si，fi与区间sj，fj不相交，则称活动i与活动j是相容的。也就是说，当sifi或sjfj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。#include void GreedyActivitySelector(int n, int *s, int *f, int *A);void PrintActivity(int n, int *s, int *f, int *A);/*/* * n:活动个数 * s:活动开始时间 * f:活动结束时间 * 假设输入的活动按结束时间递增序排列：f1 = f2 = . = fn * A:记录所选择的集合 */int n,s100,f100,A100=0;void qsort(int lx,int rx) int i,j,x,t; i=lx;j=rx; x=(i+j)/2; do while(fifx) j-; if(i=j) t=fi; fi=fj; fj=t; t=si; si=sj; sj=t; i+; j-; while(ij); if(lxj) qsort(lx,j); if(irx) qsort(i,rx);void GreedyActivitySelector(int k, int *s, int *f, int *A) int i, j; A1 = 1; j = 1; for(i = 2; i = fj) Ai = 1; j = i; void PrintActivity(int n, int *s, int *f, int *A) int i; for(i = 1; i %dn, i, si, fi); int main() int i,j; freop