鱼塘钓鱼 贪心算法

问题描述

约翰有h（1≤h≤16）个小时的时间，在该地区有n（2≤n≤25）个湖，这些湖刚好分布在一条路线上，该路线是单向的。约翰从湖1出发，他可以在任一个湖结束钓鱼。但他只能从一个湖到达另一个与之相邻的湖，而且不必每个湖都停留。 已知在最初5分钟，湖i预计钓到鱼的数量为fi（fi≥0）。以后每隔5分钟，预计钓到鱼的数量将以常数di（di≥0）递减。如果某个时段预计钓到鱼的数量小于或等于di，那么在下一时段将钓不到鱼。为简单起见，假设没有其它的钓鱼者影响约翰的钓鱼数量。

问题分析

首先分析问题，在钓鱼的过程中，访问鱼塘的顺序是单向的，但只能从一个鱼塘到相邻的下一个鱼塘，并且从一个鱼塘到相邻的下一个鱼塘路程是要耗费时间的。 以5分钟为时间周期，每一个时间周期之后鱼塘一个周期钓到鱼的数量就会减少，即每经过5分钟，fi就会减少对应的di，直到fi小于等于di时，下一周期便不会钓到鱼。 问题的关键在于怎么在各个鱼塘上分配时间来钓到更多的鱼。给定n之后，即给定鱼塘的数量，就可以把钓鱼的分为以下几个情况，在i（1，2，3，4，5…n）个鱼塘结束钓鱼进行钓鱼，由于钓鱼的方向是有向的，我们就可以知道在i个鱼塘之间钓鱼时，需要花费在路程上的时间，这时我们只需要考虑如何在i个鱼塘上分配时间，即每一个周期都选择fi最大的，看似这种方式好像违背了题目中钓鱼方向单向的要求，但并非如此

如图所示，虽然在算法过程我们先在1，2号鱼塘钓完鱼之后有返回1号鱼塘，但实际的过程则是直接在1号鱼塘上进行了两个周期，然后再进入第二个鱼塘进行钓鱼，我们的算法只是计算出在各个鱼塘中应该垂钓几次以达到最大钓鱼量。这样依次计算访问i（1，2，3，4，5…n）个鱼塘所产生的最优解最后得到最好的那一个。

代码

f[30]:表示没个鱼塘初始周期可钓鱼数量 d[30]:表示经过一个周期之后f[i]的减少量 plan[30]:表示在每个鱼塘耗费的周期数量 t[30]:表示在前往临近鱼塘的时间 best:最多的钓鱼数量

void Max(int pos,int time)
{
    int f1[30],all=0;
    for(int i=0;i<pos;i++)
    {
        f1[i]=f[i];
    }
    int p[30];
    int max_f;
    int idex=0;
    memset(p,0,sizeof(p));
    while(time>=5)
    {for(int i=0;i<pos;i++)
    {
         max_f=0;
         idex=0;
          if(f1[i]>max_f)
          {
              max_f=f1[i];
              idex=i;
          }
    }
              if(max_f>0)
              {
              all+=max_f;
              f1[idex]=f1[idex]-d[idex];
              time-=5;
              p[idex]++;}
              else
              {
                  break;
              }
    }
    if(all>best)
    {
        for(int i=0;i<30;i++)
        {
            plan[i]=p[i];
        }
        best=all;
    }
}

上述代码为了求出在第pos个池塘停止钓鱼，纯钓鱼时间为time的最多钓鱼量

 for(int i=0;i<n;i++)
    {
        int time=h*60;
       for(int k=0;k<i;k++)
       {
          time-=t[k];
       }
       Max(i+1,time);
    }

上述代码为了求出在第i个鱼塘为结束位置时，需要耗费的路途时间，从未得到纯钓鱼时间带入Max函数中，来求得最大钓鱼量。