Wx::

初步 DP 感受

难点
  • 抽象:如何提取出动态规划的参数

  • 方程:如何根据参数写出递推方程

  • 抽象出方程后即可按照抽象后的思路 “刻板” 的写出实现代码

复杂点
  • 初始化:如何选取初始值

  • 求优过程中的条件限制,和题意的特殊要求


以下可能存在不少废话...
主要在「方程实现代码」部分


抽象出参数

抽象出参数无非就是抽象出能表示任一刻的状态量,且能根据这几个状态量唯一表示出最终要求的状态即可。

列方程

  • 看局部

    • 当前状态可以怎样改变以达到另一状态?一般有多种,需要取优;
    • 状态转移的条件限制,如背包问题中当前物品重量是否超过背包容量;
  • 根据状态参数的改变和条件限制的判断,列出当前状态依赖上一状态的关系,即子问题

初始值

  • 动态规划一定要以确定的初始值开始“求表”

  • 根据题意确定初始值

方程实现代码

  • 当动态规划有了方程,就像烹饪完成的美食静待装盘

  • 即,万变不离双重循环

  • 如:
    v[i] 为 i 的价值,w[i] 为 i 的重量,C为背包容量;
    m[i][j] 为背包容量为 j,在可选物品为 i, i+1,…, n 时的 0-1 背包问题的最优值;
    可列方程如下:

    $m[i][j]= \begin{cases} { m[i+1][j] \quad\quad\quad\quad\quad\quad\quad\quad\quad {当wi>j时} } \\[2ex] { max \begin{cases} {vi+m[i+1][j-wi]} \\[2ex] {m[i+1][j]} \end{cases} \quad\quad{当wi<=j时} } \end{cases}$

    由方程可知,

    • 状态参数 i 依赖其之后的值,即 i 依赖于 i+1,所以外层 i 的循环应从后向前,即从 n-1 到 >1;
    • 状态参数 j 依赖其之前的值,即 j 依赖 j-w[i],则内层 j 的循环应从前向后,即从 0 到 w[i] 到 C;
    • 当某重循环没有依赖前后的关系时,从前到后遍历即可;
    • 有时,在动态规划核心循环中,第一重循环中还要先初始此时 i 的一个值如 dp[i][0],以便第二重循环的比较判优;
    • 当然,要注意内外层循环的边界。
    • 代码:

    // 0-1 背包主要代码:
    
    // 初始化:
    for(j=0; j<w[n]; j++)   
        m[n][j]=0;    //考虑第n个物品, 背包容量j<w[n]
    for(j=w[n]; j<=C; j++)  
        m[n][j]=v[n]; //考虑第n个物品, 背包容量j>=w[n]
    
    //考虑第i个物品:
    for(i=n-1;i>1; i--) {
        // i 有三种状态:
    
        for(j=0, j<w[i]-1;  j++)
            // 背包容量 j < w[i],不能放:
            m[i][j]=m[i+1][j];
    
        for(j=w[i], j<=C; j++)
            //背包容量 j >= w[i],可放可不放,判优:
            m[i][j]=max(v[i]+m[i+1][j-w[i]], m[i+1][j]);
        }
    

Last

这只是简述了一下我现在对动态规划的感受,还有很多不完善甚至错误的地方,也(可能)会在之后慢慢改进。
如有什么问题或建议还望指出哟。
虽然我知道没什么人会看到这个


348

评论(0

评论 取消
验证码:
搜索