首页 > 代码库 > 简单理解算法篇--动态规划

简单理解算法篇--动态规划

    动态规划方法通常用来求解最优化问题,这些问题有很多种解,但我们希望寻求最优解。

   满足两个条件既可以使用动态规划

   1.具有最优子结构

   2.子问题重叠

 至于这两点是什么意思?先看个问题

现在有个钢筋长度和价格对应的表,问:给你个长度为n的钢筋怎么卖最划算?

长度 1 2 3 4  5   6  7   8   9  10
价格 1 5 8 9 10 17 17 20 24 30

 

现在就是要把所有的切法都遍历一遍,找出最划算的切法,当你把钢筋切了一刀后,是不是变成了两段?那就要考虑的就是这两段怎么切最划算,这样会比较复杂,不妨我们这样:

把钢筋切一刀,成两半,但左边那一半不在考虑,直接按价格卖出,只考虑右边那一半,这样是不是比较简单?当然为了遍历所有切法,左边那部分是从1到n递增的。然而现在我们现在的问题就是变成切一条钢筋,左边不动,把右边又看成一条独立的钢筋切,左边不动,把右边....是不是有递归的味道了?像这样一直重复的解决同一种问题(把右边的钢筋独立看成独立的一条钢筋,继续切)就叫做子问题重叠。

至于什么是最优子结构?顾名思义就是子问题的最优解就是问题的最优解。什么意思?就是如果把钢筋分成A和B两段,那么A的最优解和B的最优解合起来就是原问题的最优解..

有人说这不是废话么?来看一个例子

现在有一个正方形,顶点为a,b,c,d,要求a->c的最短路径,是不是可以分成a->b和b->c两个子问题?a->b的最短路径当然是a->b啦,那么合起来路径就是a->b->c,这个符合最优子结构。

但是要求a->b的最长路径呢?假如按照子问题方法求解的话我们又会分成a->c和c->b两个子问题,a->c的最长路径为a->d->c,同理c->b的最长路径为c->d->a->b,那么最长路径是不是a->b?显然不是,所以这个就不满足最优子结构。

下面是实现的代码

 

        static void Main(string[] args)
        {
            int[] p = new int[]{0,1,5,8,9,10,17,17,20,24,30};    
            int n=Convert.ToInt32(Console.ReadLine());
            DateTime starDt = DateTime.Now;
            int maxp=CUTROD(p,n);
            DateTime endDt = DateTime.Now;
            TimeSpan st = endDt - starDt;
            Console.WriteLine(maxp);//最优值
            Console.WriteLine(st);//消耗时间
        }
        public static int CUTROD(int[] p, int n)
        {
            int q = -1;
            if (n == 0)
            {
                return 0;
               
            }
            else
            {
                for (int i = 1; i <= n; i++)
                {
                    q = max(q, p[i]+CUTROD(p, n - i));
                }
                return q;
            }   
        }

        public static int max(int a1, int a2)
        {
            return a1 > a2 ? a1 : a2;
        }

 

  上面的这个自顶向下方法会重复的计算一些子问题,导致时间复杂度较大,想要改善的话,就增加备忘录,就是当求出那些子问题的时候,用个数据结构把它记下来,下次要用到就直接读取就行。还有一种方法是自低向上,其实原来都是一样,就是用空间换时间

 

 

        static void Main(string[] args)
        {
            int[] p = new int[] {0,1,5,8,9,10,17,17,20,24,30};
            int n=Convert.ToInt32(Console.ReadLine());
            int[] r = new int[n+1];
            r[0] = 0;
            for (int i = 1; i <= n; i++)
            {
                r[i] = -1;
            }
            DateTime starDt = DateTime.Now;
            BottomUpCutRod(p,n,r);
            DateTime endDt = DateTime.Now;
            TimeSpan st=endDt-starDt;
            Console.WriteLine(r[n]);   //输出最优值
            Console.WriteLine(st);// 消耗时间
           
        }

        public static void BottomUpCutRod(int[] p,int n,int []r)
        {
            int q = -1;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= i; j++)
                {
                    q = max(q, p[j] + r[i - j]);
                }
                r[i] = q;
            }
        }

        public static int max(int a, int b)
        {
            return a > b ? a : b;
        }

就这样~

 

简单理解算法篇--动态规划