一辆汽车加满油后可以行驶N千米.旅途中有若干个加油站.若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油.并证明你的算法能产生一个最优解.

Question

一辆汽车加满油后可以行驶N千米.旅途中有若干个加油站.若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油.并证明你的算法能产生一个最优解.

Answer 1

#include
#define N 1000
int greedy(int d[],int n,int k)
{
int num = 0;
\x05int i=0;
\x05int s=0;
for( i = 0;i < k;i++)
\x05{
if(d[i] > n)
\x05\x05{
printf("no solution\n");
return 0;
}
}
for( i = 0,s = 0;i < k;i++)
\x05{
s += d[i];
if(s > n)
\x05\x05{
num++;
s = d[i];
}
}
printf("%d\n",num);
\x05
\x05return 1;
}
void main()
{
int i,n,k;
int d[N];
\x05printf("请输入汽车可行驶：\n");
scanf("%d",&n);
\x05printf("加油站的个数：\n");
\x05scanf("%d",&k);
for(i=0;i