一道非常经典的贪心题,我的算法不是非常符合条件。
一条水平路面,有n(2<=n<=25)个钓鱼湖,从左到右编号为1,2,3,...,n。佳佳有H(1<=H<=16)个小时的空余时间,他希望用这些时间钓到尽量多的鱼。他从湖一出发,向右走,有选择的在一些湖边停留一定的时间钓鱼,最后在某一个湖边结束钓鱼。佳佳测出从第i各户到第i+1各户需要走5*Ti分钟的路,海测处在第i个湖边停留,第一个5分钟可以调到鱼Fi,以后每再钓5分钟,鱼量减少Di.不考虑其他影响。编程求出钓最多鱼的方案。下面是我写的代码。我只考虑了和下一个湖比较,但和其他所有湖比较才能得出最好的解,我实在想不出该怎么写,望大家帮帮忙。
#include<stdio.h>
void diaoyu(void);
void juece(void);
void zoulu1(void);
void zoulu2(void);
int F[3]={5,5,5};
int D[3]={1,1,1};
int a[3][2]={0,0,0};
int H=60;
int hu=3;
int shouyi[4]={0,0,0};
int i=0;
int ci=0;
int n=0;
int t[3]={1,1,1};
void main()
{
/*for(int q=0;q<hu;q++){
for(int u=0;F[q]-u*D[q]>=D[q];u++)
a[q][1]+=F[q]-u*D[q];
}*/
juece();
printf("共钓到%d条鱼\n",shouyi[0]);
}
void juece()
{
int max=0;
int e=0;
shouyi[1]=0;
shouyi[2]=0;
shouyi[3]=0;
while(H>=0){
for(int m=0;m<hu;m++){
if(F[m]-D[m]*a[m][0]>e)
e=F[m]-D[m]*a[m][0];
}
if(e==0)
return;
if(i+1<hu&&i-1>=0){
shouyi[2]=F[i+1]-a[i+1][0]*D[i+1];
shouyi[3]=F[i-1]-a[i-1][0]*D[i-1];
}
else if(i+1==hu){
shouyi[3]=F[i-1]-a[i-1][0]*D[i-1];
}
else if(i==0)
shouyi[2]=F[i+1]-a[i+1][0]*D[i+1];
ci=(t[i]*5+5)/5;
n=a[i][0];
for(int j=0;j<ci;j++,n++){
shouyi[1]+=F[i]-D[i]*n;
}
for(int p=1;p<=3;p++){
if(shouyi[p]>max)
max=shouyi[p];
}
if(max==shouyi[1]){
diaoyu();
return;
}
else if(max==shouyi[2]){
zoulu1();
return;
}
else if(max==shouyi[3]){
zoulu2();
return;
}
}
}
void zoulu1()
{
printf("从第%d个湖走向第%d个湖\n",i+1,i+2);
H=H-t[i]*5;
i++;
juece();
}
void zoulu2()
{
printf("从第%d个湖走向第%d个湖\n",i+1,i);
H=H-t[i]*5;
i--;
juece();
}
void diaoyu()
{
printf("在第%d个湖钓鱼\n",i+1);
shouyi[0]+=F[i]-D[i]*a[i][0];
/*a[i][1]-=D[i]*a[i][0];*/
a[i][0]++;
H-=5;
juece();
}