《算法设计》课程报告课序号： 01 学号： 2012141461134姓名：刘佳玉任课教师：陈瑜评阅成绩：评阅意见：提交报告时间：2014年 6 月 16 日贪心算法1、问题描述（这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了）约翰要去钓鱼。
他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。
约翰从湖泊1开始，他可以在任何湖泊结束。
他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。
对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。
例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。
为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。
对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。
每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。
如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。
为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。
写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。
在每个湖花费的时间数必须是5的倍数。
这个问题包含多个测试案例！一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。
每个输入块由问题描述中的格式表示的。
每个输入块之间有一个空行。
输出格式包含N个输出块。
输出块之间要有一个空白行。
输入在输入中，会给你一个案例输入的数量。
每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。
输入在n=0的情况下终止。
输出对于每个测试案例，输出在每个湖花费的时间数量，以逗号分隔，为实现计划的能钓到的鱼的最大数量（你必须把整个计划输出在一行，即使超过80个字符）。
这是一个包含预期能钓到的鱼的数量。
如果存在多个计划，选择一个花尽可能长的时间在湖1的计划，即使没有鱼能钓在一些时间里。
如果不行，选择一个花尽可能长的时间湖2的计划，等等。
每个案例之间有一个空行。
2、算法分析看到这个题目后，你可能毫无思绪，怎样钓才能钓最多呢？请仔细看题，题目中说，沿湖是一条单行道，只能前进，不能后退，所以我要使前面钓的鱼最多，但如果不和后面的湖比较，怎么知道我前面掉的鱼是最佳的呢？我们不妨假设，我们只走到湖i（1<=i<=n），我们把花在路上的时间减去，这样就相当与我们可以再湖1和湖i之间任意选择一个湖钓鱼，这样每一个时间间隔我们在哪钓鱼通过比较一下不就清楚了吗，用一个循环找到最多到湖i钓鱼的最优解，然后这个问题就迎刃而解了。
3、程序源代码#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#include<queue>using namespace std;int f[30]; //能钓到的鱼的数量在某一时间块int d[30]; //在某一时间块钓鱼后湖里的鱼减少的数量int t[30]; //从湖i到湖i+1的时间int s[30]; //最佳情况下在每个湖停留的时间int fc[30]; //只到湖i钓鱼时各个湖能钓到的鱼的数量int sc[30]; //只到湖i钓鱼时各个湖停留的时间int main(){int T; //输入模块数int n; //湖的数量int h; //时间int i,j,k;int sum; //只到湖i钓鱼能钓到的鱼的总量int maxh; //从湖1到湖i能钓到的最大数量的鱼的湖 int maxn; //当前能钓到的鱼的最大数量，初始为-1； int temp; //钓鱼花的时间int kase=1; //案例数printf("输入案例的数量：\n");scanf("%d",&T);while(T--){printf("\n");printf("案例%d:\n",kase++);printf("输入湖泊的数量(0结束该组案例)：\n"); while(scanf("%d",&n)==1&&n){printf("输入钓鱼的时间：\n");scanf("%d",&h);h*=12; //以每5分钟为一个时间单位printf("输入初始时每个湖泊中的鱼的数量：\n");for(i=1;i<=n;i++){scanf("%d",&f[i]);}printf("输入每个湖泊在钓过一次鱼后鱼减少的数量：\n");for(i=1;i<=n;i++){scanf("%d",&d[i]);}printf("输入从湖泊i到湖泊i+1的时间：\n");for(i=2;i<=n;i++){scanf("%d",&t[i]);}t[1]=0; //从湖1到湖1的时间为0maxn=-1; //初始maxn的值for(i=1;i<=n;i++){for(j=1;j<=n;j++){fc[j]=f[j]; //复制能钓到的鱼的数量}for(j=1;j<=n;j++){sc[j]=0; //开始时每个湖停留的时间为0}h=h-t[i]; //除去路上用的时间就是钓鱼的时间//printf("h:%d\n",h); //查看h的值sum=0; //初始只到湖i是能钓到的鱼的总数for(k=1;k<=h;k++){maxh=1; //当前时间段能钓到最多鱼的湖for(j=1;j<=i;j++){if(fc[j]>fc[maxh]){maxh=j;}}if(fc[maxh]<=0){break; //如果最大能钓到的鱼的数量<=0，那么就停止钓鱼，把时间花在湖1}sum+=fc[maxh]; //钓到的鱼的总量fc[maxh]-=d[maxh]; //在湖maxh钓到的鱼的数量减少sc[maxh]+=5; //在湖maxn停留的时间加5}//printf("sum:%d\n",sum);if(sum>maxn) // 保存最优解{temp=0;maxn=sum;for(j=1;j<=n;j++){s[j]=sc[j];temp+=sc[j];}s[1]=s[1]+h*5-temp; //将剩余时间停留在湖1}/*for(j=1;j<=n;j++) //查看当前最优解{printf("%d ",s[j]);}printf("\n");*/}printf("输出在每个湖泊停留的时间：\n");for(i=1;i<=n;i++) //输出{printf("%d",s[i]);if(i!=n){printf(", ");}}printf("\n");printf("能钓到的鱼的最大数量: %d\n",maxn);printf("\n");printf("输入湖泊的数量(0结束该组案例)：\n"); }}return 0;}4、测试数据与运行结果样本输入12110 12 524410 15 20 170 3 4 31 2 34410 15 50 300 3 4 31 2 3样本输出45 5Number of fish expected: 31240 0 0 0Number of fish expected: 480 115 10 50 35Number of fish expected: 724 测试截图：5、算法复杂性分析与讨论课程名称：计算机算法设计与分析学生姓名：刘佳玉学生学号：2012141461134由于有三个for循环：for(i=1;i<=n;i++)for(k=1;k<=h;k++)for(j=1;j<=i;j++)算法复杂度O（n）=k*n^2。
由于这道题的n比较小，所以O（n^2）的算法也可以解决。
如果使用堆优化，可以更快，其O（n）=k*n*logn。
-10-。