贪心、递归、递推以及动态规划算法的分析与对比

 

贪心、递归、递推以及动态规划算法的分析与对比

王喆 天津市第五十五中学

【关键字】

动态规划 贪心 递归 递推 分析 说明 NOIP

【摘要】

本文通过典型例题分析出贪心算法、递归算法、递推算法以及动态规划算法的区别和相似处。以及对这几种算法的思考方法，编程方法以及“递归节省时间浪费空间，递推滚动节省空间浪费时间”的解释和举例论证。

【正文】

一、各算法的介绍

1.1贪心算法

贪心的思想可以用一句话来归纳，“每步取优”。很好理解，假设你的程序要走I=1~N共N步，那么保证你的第I步走出的是当前这一步的最优值。这样的解题 方法叫做贪心算法。可见贪心算法并不是一个全面的枚举方法而是若干结果中的一种，仅仅一种而已。但这种算法是不是最优解它就不能完全保证了。

1.2递归算法

一般每个可以使用递归算法求解的题目都可以写出一个递归函数。假设这个函数是F（），那么F（）应该为你可以表示你的解。而题目的主要问题就是把一个大问题转换为若干个性质相同的 子问题。注意是性质相同，因为只有性质相同我们才能使用同一个函数来表示。而求解的过程是从最后一步，当然每一步都会用到比自己要小的子问题的值，那么要 调用程序来求出这些子问题的解，一步步返回最后得到最后的问题的解。也可以理解为求解过程是“反向”的。因为变量会是逐渐变小的。

1.3递推算法

与递归算法一样，必定会写出一个转移方程，而每个可以用递归方法解决的问题都可以用递推方法解决。我们要做的依然是把大问题转变为性质相同的 子问题的过程。而求解过程与递归方法正好相反，是从最小规模的子问题开始求解，最后求到最大规模的解。与递归不一样的是，递归可以只求我们所需要的子问题 的解，而递推算法在每一步计算求解的过程中并不知道下一步需要用什么样的子问题的值，于是程序必须把所有的可能性都求出来。造成了很多的计算浪费。但递推 算法有一个递归算法永远做不到的优势就是“滚动性”。当递推算法求解完第一行的子问题的时候进行第二行的处理，第二行会用到上一行的子问题值。当处理第三 行的时候第一行的值就没有用了，所以我们可以把单数行的值都存到第一各数组里，双数行的值都存到第二个数组里。这样可以就可以实现滚动，原来原本要开 [1..n,1..n]大小的数组现在就可以只开[1..n,1..2]大小的数组了，把空间复杂度从O(N²)的复杂度变为O(2N)的复杂度。这就是所谓的“递推省空间费时间，递归省时间费空间”的道理。

1.4动态规划算法

动态规划算法，动态规划算法可以理解为是递归算法的一个延伸。因为单纯的递归算法是会出现很多子问题的重叠的，这样还是会造成同一问题的重复运算。所以我 们要找一个办法来避免重复的运算。于是就出现了动态规划。简单地说，动态规划依然是把一个大问题分为若干性质相同的子问题，而这些子问题里面会有若干的重 叠。（下面的例题举例）。为了当出现子问题重叠的时候不重复运算。我们就需要把所有的已经求出的子问题都存下来，判断这个子问题是否已经算过，算过了就不 要再算了。如果没算过就算一遍下次在遇到这个子问题就可以不算了。因此我们必须开出一个大小为[1..N,1..N]的数组来存储，又因为每次都有可能会 遇到不同的行的子问题，所以我们必须把数组全部留住，所以就不能实现递推算法的“滚动性”。但动态规划算法可以节省大量的时间。假设所有的子问题都不重叠 它的时间复杂度会和递归一样。而如果优有大量的子问题重叠，那么会发现时间复杂度会有明显的降低。可以提高运算效率，缩短运算时间。

二、           用树状图直观体现动态规划的子问题分配

 

（图一）

 

       从上面的树状图我们可以很清楚的看到，每一个大的问题是会被当作树根划分为若干个子问题的，每个子问题又会作为一个子树的树根被划分为若干个子问题。只有 找到最后一层的问题时才会停止，我们把这样的最后一层称为“边界”。一般都是当变量为0或1或什么值时返回一个固定的值。使用递归就要加上一句判断，如果 使用递推的话就要单独初始化，单独赋值。

下面就对典型的例题来分析贪心法的不足与动态规划子对于重叠子问题的计算。

三、           典型例题分析

采药

(medic.pas/c/cpp)
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。

3、1对贪心算法的反例

首先我们用贪心的思想来规划这道题的话，我们会按照顺序每次取优解假设我们现在有这样的一组数据：

100 5

50 100

1 50

2 80

1 50

96 50

无论我们是按照价值的大小排序还是按照价值于时间的比值排序我们都得不到最优解。所以，贪心法并不适用于这道题。于是贪心方法被直接PASS。所以我们试着使用递归和动态规划方法来解决。

3.2对递归递推算法的数学模型介绍

根据题目我门可以把总的大问题写成一个函数F(T,M)。我们可以把这个函数这样定义，F（I,J）表示拥有T时间，有J个未采药材所可以获得的最大价值。

如果把函数像上面的样子定义的话，很容易我们就可以把一个大问题分解成若干个性质相同的子问题，从而我们就可以用地归和动态规划来解决。这样呢，我们就可以写出一个递归转移方程，来解释F（I,J）

解 释一下，对于每一个药材都有采它所需要的时间，当这个时间比整个子问题的J也就是所剩余的时间要大的时候我们就没有时间去采这个药材，无论整个药材是多么 的有价值。所以，在方程中规定，只要是a[i-1,j]>j则我们就硬性结束，直接返回F[i-1,j]的值。当这个采这个药材所需要的时间小于剩 余的时间时，我们就出现了两种解决办法。第一采这个药，第二不采。而我们要做的是在这两个值里面挑一个最大的来作为这个子问题的解。而由于这道题由于药的 顺序和不影响最后的解，所以我们可以忽略最后的顺序。我们可以从第M个开始一直到第1个。

3.3 介绍单纯递归方法的函数实现

根据上面的转移方程我们很容易的就可以写出递归函数

       示例函数：

       Function try1(i,j:Integer):Longint;（*定义函数*）

Var（*共需要两个局部变量*）

            max1,max2:Longint;

Begin

            If (i=0) Or (j=0) Then Begin（*边界判断*）

                  try1:=0;（*满足边界则返回0，直接退出*）

                   Exit;

            End;

            If i>=a[j].t Then max1:=try1(i-a[j].t,j-1)+a[j].v Else max1:=0;（*判断时间是否足够，足够则求出采这个药之后的最大价值*）

            max2:=try1(i,j-1);（*直接求不采的最大价值，（多说下，这里J-1一定不会减到小于0的情况因为前面有边界条件限制了）*）

            If max1>max2 Then try1:=max1 Else try1:=max2;（*判断出个最大值然后返回*）

End;

3.4 解释单纯递归方法的计算浪费和效率低的原因

       根据上面的转移方程我们假设样例为

100 5

1 50

2 80

1 50

50 100

96 50

用树状图来表示就会很清晰

很容易看出来在这棵树的第四层就出现了重复情况。子问题出现了重叠，如果我们这个样例的话这棵树只有7层。可想而知当一个数据M=100的时候。会出现多少同样的情况。如果都算一遍，我们是不是浪费了很多很多时间呢？

       所以我们才要想办法避免这种情况的出现，否则很多的时间都会浪费在“无用功”上，使得我们程序的效率会降低很多。很好的一个解决办法就是把每次所求出来的 子问题的值都用一个数组存下来，这样我们可以判断这个子问题是否处理过，如果处理过了我们就不要再去处理，如果没处理我们就处理它。这就是动态规划的思 想。所以我们必须要开出一个大小为[0..100,0..1000]的数组来存储这些子问题。

3.5  给出动态规划方法解决的样例程序程序

样例程序解决：

Program medic;

（**************************medic.pas **************************）

（********WangZhe,55^Th senior high school of Tianjin********）

（**************************2008-8-21***************************）

Type (*定义数组类型，.t表示时间，.v表示价值*)

                   re=record

                       t:Integer;

                       v:integer;

                    End;

Const (*关联输入输出文件*)

            Infile='medic.in';

outfile='medic.out';

Var （*变量定义*）

            m,t,i:Integer;

          data,s:Array[0..100,0..1000] Of integer;（*动态规划存储数组*）

          a:Array[0..100] Of re;（*输入数据数组*）

Procedure try1(i,j:Integer);（*动态规划主过程*）

Var

max,max1,l:integer;（*所需要的两个局部变量*）

Begin

  If (i=0) Or (j=0) Then Begin（*判断边界*）

    Data[i,j]:=0;（*处理边界*）

    Exit;

  End;

  If data[i-1,j]=-1 Then Try1(i-1,j);（*很关键的一步判断问题是否已经求过，其中-1仅仅是一个空标记，因为这道题不可能出现负值所以我们就定义-1为标记，这个标记不一定要用多少只要是解题中不可能出现的标记就好*）

  Max:=Data[i-1,j];（*求出不采这个药的最大价值*）

 

  If j>=a[i].t Then Begin（*判断时间是否足够，足够则求出采这药的最优值*）

    If Data[i-1,j-a[i].t]=-1 Then try1(i-1,j-a[I].t);

Max1:=data[i-1,j-a[i].t]+a[i].v;

Else

  Max1:=0;(*不够就付个0就可以了*)

End;

    If max< max1 Then max:=max1;(*判断出一个最大值来*)

  data[i,j]:=max;（*把最大值付给DATA*）

  End;

Begin(*主程序*)

  Assign(input,infile);（*文件关联*）

  Assign(output,outfile);

  reset(input);

  rewrite(output);

  fillchar(data,sizeof(data),$ff);（*数组清零！这步很重要！！多打几个叹号！这个如果不标记那么是求不出值的。*）

  readln(t,m);（*读入两个控制值*）

  For i:=1 To m Do readln(a[i].t,a[i].v);（*读入数据*）

  try1(M,t);（*动态规划求解*）

  writeln(data[m,t]);（*输出最优解*）

  close(input);（*关闭文件*）

  close(output)

End.

3.6递推方法样例程序的介绍和注释

从这个程序和上面给出的递归的程序对比一下就看的出来，动态规划的程序就是加入了一个存储和判断。其他的思想上和数学模型上都是一样的。

   下面给出一个递推滚动的程序大家对比看看。（上面注释过的我就不注释了，只注释出区别）

Program medic;

Type re=record

     t:Integer;

     v:integer;

End;

Const infile='medic.in';

      outfile='medic2.out';

Var m,t,i,j,n,k,max1:Integer;

    data:Array[0..2,0..1000] Of integer;（*因为滚动，开数组只需要开2个就行了*）

    a:Array[0..100] Of re;

Begin

  Assign(input,infile);

  Assign(output,outfile);

  reset(input);

  rewrite(output);

  fillchar(data,sizeof(data),$ff);（*可以不清零，不过保险起见还是清*）

  readln(t,m);

  For i:=1 To m Do readln(a[i].t,a[i].v);

  For i:=0 To t Do（*处理边界，也可以叫做“预处理”*）

    If a[1].t<=i Then Data[1,i]:=a[1].v Else data[1,i]:=0;

  For i:=2 To m Do（*递推用循环就可以实现，不用再写过程了*）

    For j:=0 To T Do Begin

      If i mod 2 =1 then n:=1 Else n:=2;（*控制滚动，这一步很重要，单数用1数组，双数用2数组*）

      If n=1 Then k:=2 Else k:=1;（*还是滚动控制*）

      Data[n,j]:=Data[k,j];

      If (j>=a[i].t) Then Begin（*这个地方的思想是一样的，判断时间是否足够*）

        max1:=Data[k,j-a[i].t]+a[i].v;

        If max1>data[n,j] Then Data[n,j]:=max1;（*求最大值保存*）

      End;

  End;

  writeln(data[n,t]);

  close(input);

  close(output)

End.

3.7动态规划递归和递推方法的区别与联系

从上面的程序我们可以看的出来数学模型上，递归递推没有什么区别，而递推可以实现滚动，我们可以节省空间复杂度，使空间复杂度降低了50倍。而时间上势必会多浪费些。

【结语】

       通过作者的介绍，我想读者会很容易的看出来这集中方法的区别和联系。从作者自己的经验来讲，我觉得处理一道这样的题。我们首先要想想是否可以适用贪心算法 来解决，由于贪心算法是“一条链”式的处理算法，所以无论空间复杂度还是时间复杂度都是很低的。拿到一道题我们可以先试着用贪心算法试验一下是否可以用别 的反例来推翻贪心算法。判断题目不可以用贪心算法来解决了以后我们就要静下心来，再仔细看一遍题目，总结递归转移方程。因为总结转移方程是解题的最重要的 一步。如果你的编程技巧和熟练度足够的话，只要你的转移方程写对，剩下来的就只剩“抄”程序了，会很快完成题目的。作者也是每年都要参加NOIP的选手， 所以我很希望能与各位读者有交流的机会。贴出我的博客，欢迎大家来交流！http://skysummerice.

【特别鸣谢】

感谢天津FNOI的教练藤伟老师给予作者的指导与启发