| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 644 人关注过本帖
标题:[求助]这个贪心算法题的完善的代码怎么写?
只看楼主 加入收藏
张德峰
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2006-6-6
收藏
 问题点数:0 回复次数:0 
[求助]这个贪心算法题的完善的代码怎么写?

一道非常经典的贪心题,我的算法不是非常符合条件。
一条水平路面,有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();
}

搜索更多相关主题的帖子: 钓鱼 编程 经典的 佳佳 时间 
2006-06-07 13:13
快速回复:[求助]这个贪心算法题的完善的代码怎么写?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025823 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved