Net Core教程

动态规划_C#

本文主要是介绍动态规划_C#,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

参考网址:https://blog.csdn.net/lvcoc/article/details/104167648

先不管动态规划,先看斐波那契数列

斐波那契数列:F1=Fn-1+Fn-2

分别用递归和非递归实现一下

递归

//递归
public int FibnacciA(int n)
{
  int res;
  if (n == 1 || n == 2)
  res = 1;
  else
  res = (FibnacciA(n - 1) + FibnacciA(n - 2));
  return res;
}
非递归

//非递归
public int FibnacciB(int n)
{
  List<int> f = new List<int>() { 0, 1, 1 };//斐波那契数列先初始化前3个特殊的
  if (n>2)
  {
    //n=3 计算1次 n=5 计算3次
    for (int i = 0; i < n-2; i++)
    {
      int fl= f.Count;
      f.Add(f[fl - 1] + f[fl - 2]);
    }
  }
  return f[n];
}
经过测试都是对的,但是重点不是这个,重点是运行时间

 

很明显非递归快的多,而且递归50或者100的时候,我直接卡死了。为啥

因为递归方法里有很多子问题的重复计算,而且数字越大,子问题重复越严重

而非递归的方法里子问题不会重复,而是存起来了

那么非递归的那个方法就可以称为动态规划(DP)

能够动态规划的问题需要两个关键点 1有递推式 2有重复子问题

钢条切割问题

某公司出售钢条,出售价格与钢条长度之间的关系如下表:

 

问题:现有一段长度为n的钢条和上面的价格表,求切割钢条方案,使得总收益最大。

举个栗子,下面列出的是0-10的最优收益

 

长度1的时候不用切就是1,长度2的时候可以切1+1,可以不切5,得到5,长度3的时候,首先不切是8,切1和2,2还可以切,但是2其实我们之前已经切过了,最优是5,所以不用继续考虑了,1和2就是1+5=6,最优是8,直接看长度8的时候,可以不切20,

可以切1和7,7之前也考虑过了是17,所以1和7就是1+18=19,最后发现最优是2和6,也就是5+17=22。

到这里其实我们发现这是一个递归的问题。那么我们需要一个递推式

递推式 R(n)=Max(P(n),R(1)+R(n-1),R(2)+R(n-2),.....,R(n-1)+R(1));

//递推式 R(n)=Max(P(n),R(1)+R(n-1),R(2)+R(n-2),.....,R(n-1)+R(1));
public int CutRodA(int n)
{
  int[] P = new int[] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//价格表
  int res = 0;
  if (n == 0)
  res= 0;
  else
  {
    res = P[n];//不切
    for (int i = 1; i < n; i++)
    {
      res = Mathf.Max(res,CutRodA(i)+CutRodA(n-i));
    }
  }
  return res;
}
测试一下

 

其实这个递推式还可以再简化,就是

从钢条的左边切割下长度为i的一段,只对右边剩下的一段继续进行切割,左边的不再切割

递推式就变成

public int CutRodB(int n)
{
  int[] P = new int[] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//价格表
  int res = 0;
  if (n == 0)
  res = 0;
  else
  {
    res = P[n];//不切
    //1<=i<=max
    for (int i = 1; i < n+1; i++)
    {
    res = Mathf.Max(res, P[i] + CutRodA(n - i));
    }
  }
  return res;
}
测试一下

 

但是 ,这两种方法都是自顶向下递归,会产生子问题重复,而且也是钢条越长,子问题重复越厉害

自顶向下从n开始,问题越分越细

也就是4需要3210,3需要210,越分越细

那么1有递推式,2有重复子问题,我们就可以用动态规划了,自底向上实现

//自底向上
public int CutRodC(int n)
{
  int[] P = new int[] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//价格表
  List<int> r = new List<int>();//还是需要一个列表存子问题
  r.Add(0);//0长度收益0
  for (int i = 1; i < n + 1; i++)//自底向上从1开始存子问题
  {
    int res = 0;//每次需要重新计算收益
    //利用的是简化的递推式2,对于这个循环i就是n,j就是i
    for (int j = 1; j < i + 1; j++)
    {
      //本来r[i-j]也就是n-1,是需要递归,但是因为我们已经存过了,直接取就好了
     res = Mathf.Max(res,P[j]+r[i-j]);
    }
    r.Add(res);
  }
  return r[n];
}
我尽力注释了,但是还是可能有点绕,需要好好理解

测试一下他们的时间

 

动态规划明显快了很多

如果你想测试更长的钢条,你需要自己定制一个相应长度的价格表
————————————————
版权声明:本文为CSDN博主「lvcoc」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/lvcoc/article/details/104167648

这篇关于动态规划_C#的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!