贪心法例题讲解

旅行家的预算(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 solution

sample input

sample output

problem source

/ 测试用例。

分析：需要考虑如下问题：

1）出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？

2）汽车行程到第几站开始加油，加多少油？

可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。

通过分析，我们可以选择这样的贪心标准：

对于加油站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。

1 若value[i]>value[k]，则按贪心方案，第i站应加油为。

t=（way[k]-way[i]）/m-over[i]。

若t若t>x[i], 则预示着，汽车开到油站k，仍然有油剩余。假设剩余w加仑汽油，则须费用value[i]*w，如果w加仑汽油在油站k加，则须费用value[k]*w，显然value[k]*w2 若value[i] t=c-over[i即加满油）。

若t若t>x[i]，则表示在第i站的不加满油，而将一部分油留待第k站加，而value[i]综合上述分析，可以得出如下算法：

i :=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 汽车到达终点；

方法一：#include<>

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++)

void wo()

int j,k,min1,min2;

rest=cost=k=0;

while(k<=n)

if(j==k)

if(min1!=0)else

int main()

init();

wo();printf("%0.2lf",cost);

2、活动安排问题

问题描述] 假设有一个需要使用某一资源的n个活动组成的集合s，s=。该资源一次只能被一个活动所占用，每一个活动有一个开始时间bi和结束时间ei (bi≤ei)。若bi≥ej或者bj≥ei，则活动i和活动j兼容。

你的任务是：选择由互相兼容的活动组成的最大集合（活动最多）。

输入格式]

输入文件名为：共n+1行，其中第1行为n，第2行到第n+1行表示n个活动的开始时间和结束时间（中间用空格隔开），格式为：

nb1 e1

bn en输出格式]

输出文件名为：共两行，第1行可举办活动的个数，第2行为最大集合中的活动序号，每个数据之间用一个空格隔开。按活动先后输出。

样例输入]

样例输出]

活动安排问题。

一个由需要使用某一资源的n个活动组成的集合s = 该资源一次只能被一个活动占用。每个活动i有个开始时间s[i]和结束时间f[i]，且s[i]

如果[s[i], f[j])与[s[i], f[j])互不重叠，则称活动i和j是兼容的。活动安排问题就是要选择一个由互相兼容的问题组成的最大集合。

活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

设有n个活动的集合e=，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si#include <>

void greedyactivityselector(int n, int *s, int *f, int *a);

void printactivity(int n, int *s, int *f, int *a);

* n:活动个数。

* s:活动开始时间。

* f:活动结束时间。

* 假设输入的活动按结束时间递增序排列：f[1]

* a:记录所选择的集合。

int n,s[100],f[100],a[100]=;

void qsort(int lx,int rx){

int i,j,x,t;

i=lx;j=rx;

x=(i+j)/2;

do{while(f[i] while(f[j]>f[x]) j--;

if(i<=j){

t=f[i];

f[i]=f[j];

f[j]=t;

贪心法例题讲解

2024年税法例题

光纤例题讲解,习题

砌体结构例题讲解

其他用户还读了