汽車加油問題貪心演算法

⑴ 汽車加油問題 貪心演算法（C++）

第一次加滿油

然後在能到達的最遠的加油站再加滿油

如此反復, 最後到達目的地

如果中間某次加油後不能到達下面任何一個加油站

那麼就無解

⑵ 求貪心演算法汽車加油問題程序

#include<iostream.h>
#include<fstream.h>配鍵
void addoil(int &n,int &k,int *a,int *c,bool *b1,bool *b2,int &count)
{
int oil=n;
//count=0;
int i=0;
//a=new int[k+1];
b1=new bool[k+1];
c=new int[k+1];
b2=new bool[k+1];
while(i<=k)
{

if(oil-a[k]<a[k+1])
{
oil=n;
count++;
c[k]=k;
b1[k]=true;
}
if(a[k]>n)
{
b2[k]=false;
break;
}
if(oil-a[k]>a[k+1] && a[k]<=n)
i++;
}
}
void main()
{
int n,k;
int count=0;
int *a,*c;
bool *b1,*b2;
ifstream fin;
fin.open("D:\\input.txt");
fin>>n>>k;
a=new int[k+1];
b1=new bool[k+1];
c=new int[k+1];
b2=new bool[k+1];
for(int i=0;i<k+1;i++)
fin>>a[i];
addoil(n,k,a,c,b1,b2,count);
ofstream fout("D:\\output.txt");
for(int j=0;j<k+1;j++)
if(b2[j]=false)
{
fout<培謹巧<晌彎"No Solution";
return;
}
for(int l=0;l<k+1;l++)
if(b1[l]=true)
{
fout<<"should add oil at the "<<c[k]<<"service station"<<endl;
}
fout<<count;
}

⑶ 智力題！求教高手！汽車加油問題

加12次油～ 12次
具體分析～
只看前面500米～ 把500公里 沒隔100公里定為一個點
也就是起點是加油站 後面五個點為油桶
你分完段後從加油站出發到第一個油桶來回要用去200公里的油則你只能存300公里的油，到底存多少一開始誰都不知道～所以我們要從後往前推
你若想行駛玩最後500公里則你車里必須在500公里處時油是滿的
那麼你在第4油桶必須存800公里的油 從第4油桶往第5油桶存油來回消耗200公里的油 則存300公里的油 再從第4油桶到第5油桶要消耗100公里的油
第5油桶有300公里的油 則車里還要有200公里的油 算一下你到第四油桶往第五油桶行駛時必須要有800公里的油
一次類推 第三油桶往第四油桶行駛時要有1300公里的油
第二油桶往第三油桶行駛時要有2200公里的油
第1油桶往第2油桶行駛時要有3700公里的油
加油站往第一油桶運11次是3300公里的油 回去加油 回到第一桶油的位置車上還有400公里的油 加起來剛好3700公里的油 總共加了12次