• <menu id="ckmo6"></menu>
  • <input id="ckmo6"><u id="ckmo6"></u></input>
    <menu id="ckmo6"></menu>
  • <input id="ckmo6"><acronym id="ckmo6"></acronym></input>
  • 动态规划总结

    ---恢复内容开始---

    动态规划来源于分治法,本质是为了节省递归栈所消耗的时间/空间,同时把相同的子问题的解记录下来,防止系统做重复工作,浪费时间。

    一般用动态规划做题时候,要从分治法开始,进一步考虑是否存在相同的子问题解且解是否重复,如果有可以采用动态规划求解【当然递归方程还是要写的】。

    动态规划的递归方程和分治法略有不同,动态规划的递归一般都用二维数组储存数据【当然也有用一维数组甚至一个变量的,不过都是二维数组的简化版】,首先我们要弄清楚m[i][j]的几何意义,然后根据题目要求写出m[i][j]=...【一般都是和m其他元素挂钩的】,这就是动态规划的递归方程。

    一般写递归方程分为以下几种情况

    1.确定规划起点终点,规划方向确定

    例题:

    7-1 数字三角形 (30 分)
     

    给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。

    QQ截图20170929023616.jpg

    输入格式:

    输入有n+1行:

    第 1 行是数字三角形的行数 n,1<=n<=100。

    接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。

    输出格式:

    输出最大路径的值。

    输入样例:

    在这里给出一组输入。例如:

    5 
    7 
    3 8 
    8 1 0 
    2 7 4 4
    4 5 2 6 5

    输出样例:

    在这里给出相应的输出。例如:

    30

    一般遇到这种题只需要从终点入手,就会发现到终点的路径值只能是m[i-1][j]或者m[i-1][j-1]再加自己的值,这样子到终点问题就被转化成为了到达倒数第二层格子的值,以此类推。

    #include<iostream>
    using namespace std;
    
    int main()
    {
        int n,i,j;
        cin>>n;
        int a[101][101];
        int d[101][101];
        for(i=1;i<101;i++)
        {
            for(j=1;j<101;j++)
            {
                a[i][j]=0;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                cin>>a[i][j];
            }
        }
    
        for(j=1;j<=n;j++)
        {
            d[n][j]=a[n][j];
        }
        for(i=n-1;i>=1;i--)
        {
            for(j=1;j<=n;j++)
            {
                if(d[i+1][j]>d[i+1][j+1])
                {
                    d[i][j]=d[i+1][j]+a[i][j];
                }
                else
                {
                    d[i][j]=d[i+1][j+1]+a[i][j];
                }
            }
        }
        cout<<d[1][1];
    }

    当然不创建d数组而直接覆盖a数组也是可以的

    结论:这种确定方向的题,从终点把每个情况想清楚,然后得出最大最小即可。

    其他问题:商人过路费,求子段最小操作数问题

    2.方向不确定或者自由,起终点确定:

    3-2 租用游艇问题 (22 分)
     

    题目来源:王晓东,《算法设计与分析》

    长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

    输入格式:

    第1 行中有1 个正整数n(n<=200),表示有n个游艇出租站。接下来的第1到第n-1 行,第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。

    输出格式:

    输出从游艇出租站1 到游艇出租站n所需的最少租金。

    输入样例:

    在这里给出一组输入。例如:

    3
    5 15
    7

    输出样例:

    在这里给出相应的输出。例如:

    12

    这道题同样从终点想到起点,从i到n,要么直接过去,要么经过一堆中途站,而这些中途站所在值可以作为子问题求解。

    递归方程:m[i][j]从第i个站出发到j=max(m[i][k]+m[k][j],m[i][j])其中k<n,大于y一般都用for循环求出结果。

    #include<iostream>
    using namespace std;
    int main()
    {
        int n,i,j,k;
        int yangtzeriver[200][200];
        cin>>n;
        for(i=0;i<n;i++)
        {
            yangtzeriver[i][i]=0;
            
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                cin>>yangtzeriver[i][j];
                
            }
        }
        //cout<<"e";
        for(i=n-1;i>=0;i--)
        {
            //cout<<" d";
            for(j=i+1;j<n;j++)
            {
                //cout<<yangtzeriver[i][j]<<" "<<(yangtzeriver[i][j-1]+yangtzeriver[j-1][j]);
                
                int mini=min(yangtzeriver[i][j],yangtzeriver[i][j-1]+yangtzeriver[j-1][j]);
                for(k=i+1;k<j;k++)
                {
                    int q=min(yangtzeriver[i][j],yangtzeriver[i][k]+yangtzeriver[k][j]);
                    //cout<<yangtzeriver[i][j]<<" "<<(yangtzeriver[i][k]+yangtzeriver[k][j])<<" ";
                    if(q<mini)
                    {
                        mini=q;
                    }
                }
                //cout<<mini;
                yangtzeriver[i][j]=mini;
            }
        }
        cout<<yangtzeriver[0][n-1];

    如:3-1,3-3

    3.方向确定,起终点不自由

    一般采用方法是记录最大值

    如:

    3-2 租用游艇问题 (22 分)
     

    题目来源:王晓东,《算法设计与分析》

    长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

    输入格式:

    第1 行中有1 个正整数n(n<=200),表示有n个游艇出租站。接下来的第1到第n-1 行,第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。

    输出格式:

    输出从游艇出租站1 到游艇出租站n所需的最少租金。

    输入样例:

    在这里给出一组输入。例如:

    3
    5 15
    7

    输出样例:

    在这里给出相应的输出。例如:12

    一般遇到这种题,就不要把思维局限在终点。要这样想:从任意一个数开始,如果前面一堆数<0,
    那以他为底的尾串就是自己,否则是前面一堆数加上这个数得到递归方程m[j]=max(m[j-1]+num[j],num[j]),
    或者if num[j]<0,m[j]=num[j],else m[j]=(m[j-1]+num[j])
    代码省略 自己看书
    //看书
     
          
    (当然 直接分治法方法加备忘录 也是可以的)

    4.都没有 自己挑 如0-1背包
    0-1背包:给定种物品和一个容量为的背包,物品的重量是,其价值为,背包问题是如何使选择装入背包内的物品,使得装入背包中的物品的总价值最大。其中,每种物品只有全部装入背包或不装入背包两种选择。
    这种题目二维数组的代表意义会十分的奇怪,比如说在0-1背包中,一个数代表从几号物品开始装,另一个数代表容量。
    把二维数组顺序搞明白后,就会明显发现m[i][j]=max(m[i+1][j-i的价值],m[i+1][j])【前提:能装的下(j>i的价值),装不下直接m[i+1][j]】
    然后把最后一行填好,就能往上填表了


    #include<iostream>
    using namespace std;
    int main()
    {
        int n,capity,i,j;
        cin>>n>>capity;
        int item[100],percapity[100];
        for(i=0;i<n;i++)
        {
            cin>>item[i];
            cin>>percapity[i];
        }
        int bag[100][100];
        for(j=0;j<=capity;j++)
        {
            if(j<percapity[n-1])
            {
                bag[n-1][j]=0;
            }
            else bag[n-1][j]=percapity[n-1];
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=1;j<=capity;j++)
            {
                if(j>=percapity[i])
                {
                    bag[i][j]=max(bag[i+1][j],bag[i+1][j-percapity[i]]+item[i]);
                }
                else bag[i][j]=bag[i+1][j];
            }
        }
        cout<<bag[0][capity];
    }
     
          

    一般情况下,我们可以根据表之前的结果得到m[i][j]的结果,通常需要比较i,j和递归式里面i,j的关系,从而得到i和j在填表for循环里面的顺序,从而求i和j究竟递增,还是递增。一般递归式里面i比原i大递减,否则递增,j同理。

    相关文章
    相关标签/搜索
    每日一句
      每一个你不满意的现在,都有一个你没有努力的曾经。
    公众号推荐
       一个历史类的公众号,欢迎关注
    一两拨千金
    香港精选免费资料大全 高淳县| 平顺县| 灵武市| 仁化县| 托克逊县| 大宁县| 开平市| 海宁市| 台江县| 克拉玛依市| 明星| 微山县| 高青县| 新安县| 七台河市| 东阿县| 高安市| 邳州市| 离岛区| 怀宁县| 衡水市| 瑞丽市| 澄城县| 花莲县| 浦东新区| 佛冈县| 六枝特区| 东乌珠穆沁旗| 自贡市| 南岸区| 韩城市| 涟源市| 扬中市| 喀喇| 响水县| 噶尔县| 临沂市| http://fa.hz0j1r2vo.fun http://fa.hz0j0r1vo.fun http://fa.hz0j2r3vo.fun http://fa.hz0j0r5vo.fun http://fa.hz0j0r3vo.fun