首页 > 代码库 > 简单理解算法篇--动态规划
简单理解算法篇--动态规划
动态规划方法通常用来求解最优化问题,这些问题有很多种解,但我们希望寻求最优解。
满足两个条件既可以使用动态规划
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;
}
就这样~
简单理解算法篇--动态规划