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

旅行家的预算(acm) 旅行家的预算? Problem description 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距Di、每升汽油价格 Pi（ i＝l，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.95?Problem Source // 测试用例275.6? 11.9?? 17.4? 2.82102.0? 2.9220.0?? 2.2142.54275.6? 11.9?? 10.4? 2.83 102.0? 2.1160.2? 2.3220.0? 2.262.99分析：需要考虑如下问题： 出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？ 汽车行程到第几站开始加油，加多少油？ 可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准： 对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。 对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。 贪心算法证明如下： 设定如下变量： Value[i]：第i个加油站的油价； Over[i]：在第i站时的剩油； Way[i]：起点到油站i的距离； X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。 首先，X[1]≠0，Over[1]=0。 假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。 若Value[I]Value[k]，则按贪心方案，第I站应加油为 T=（Way[k]-Way[I]）/M-Over[I]。 若TX[I]，则汽车无法从起点到达第k个加油站；与假设矛盾。 若TX[I], 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*WValue[I]*W。 若Value[I]Value[k]，则按贪心规则，须加油为 T=C-Over[I] （即加满油）。 若TX[I]，则表示在第I站的加油量会超过汽车的实际载油量，显然是不可能的。 若TX[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]Value[k]，所以这样费用更高。 综合上述分析，可以得出如下算法： 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 汽车到达终点； 方法一： #includestdio.h double p[101],dist[101]; 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,p[0],N); dist[N+1]=box;p[N+1]=0;dist[0]=0; for(i=1;i=N;i++) { scanf(%lf%lf,dd,pp);