【算法导论】动态规划(一)钢条切割

1. 动态规划(Dynamic programming)

这里programming指的是表格,而非编程。动态规划通常用来求解最优化问题

与分治法对比:

  1. 相同点:都是通过子问题组合求解原问题
  2. 不同点:分治法将问题划分为不相交的子问题,求解再合并,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题,此时如果用分治法就会出现重复计算求解。为了避免重复动态规划对子问题只求解一次,将其保存在表格中,从而无需每求解一个子子问题时重复计算。

2. 求解步骤

  1. 刻画最优解的结构特征
  2. 递归定义最优解的值
  3. 计算最优解的值,通常采用自底向上的方法
  4. 利用计算出的信息构造最优解

其中不是所有的题目都会要求4,仅仅要求3,要求4的时候,我们需要在得到3的同事维护一些额外的信息来求出4。

看到这四个步骤的时候,还是挺懵逼的,继续往下看=.=

3. 钢条切割问题

问题

Serling公司购买一根长钢管,将其切割成短钢管出售,给定钢管长度和对应的价钱如下表:

问题要求根据上面的价格,给出最佳的切割方案,使得收益最大。

以n=4为例,可以将钢条切割成如下图所示的8种情况,其中收益岁大的是(c):

思路

钢条长度为n时,共有$2^{n-1}$种分割方式。

  1. 递归

    把长度为n的钢条切割问题转化为:将钢条从左边切下长度为i的一段,对右边剩下的长度为n-i的钢条进行进一步的切割。

    CUT-ROD(p,n)//p:价格数组,n:钢条长度
    1 if n==0:
    2 return 0
    3 q=MIN
    4 for i = 1 to n:
    5 q=max(q,p[i],CUT-ROD(p,n-i))
    6 return q

    当n=4时,上面递推方式的工作量如图所示,复杂度为$T(n)=2^n$

  2. 动态规划(DP)

    可以看出来用上面递归的方式计算,中间会重复求解相同子问题。使用动态规划,仔细安排求解顺序,对每个子问题只求解一次所以,并把结果保存下来,供后续使用避免重复计算。

    ​ 对于钢条切割的问题,我们可以将长度为n的钢条切割问题转化为规模更小的子问题:当完成首次切割后,将两段钢条看成两个独立的钢条切割问题,通过组合两个相关子问题的最优解,选取组合收益最大者,构成原问题的最优解。

    因此,将长度为n的钢条切割成两段,共有下面n种切割方式,求解下面n个子问题的最优解,再选取其中最大的作为原问题的最优解。

    ​以n=4为例:

    $r_1=1$

    $r_2=max(p_2,max(r_1)+max(r_1))=max(5,1+1)=5$

    $r_3=max(p_3,max(r_1)+max(r_2))=max(8,5+1)=8$

    $r_4=max(p_4,max(r_1)+max(r_3),max(r_2)+max(r_2))=max(9,8+1,5+5)=10$

    ​ 动态规划两种实现方法:

  • 自顶向下:

    仍按照递归的方式实现,过程中保存每个子问题的解,后续过程中先检查是否已经保存过此解,如果是,直接返回保存的值。就好像带了一个“备忘录”。

    memorized-CUT-ROD[] = MIN//用于记录子问题结果
    CUT-ROD(p,n)//p:价格数组,n:钢条长度
    1 if memorized-CUT-ROD[n] > 0:
    2 return memorized-CUT-ROD[n]
    3 else
    4 for i = 1 to n:
    5 q=max(q,p[i],memorized-CUT-ROD(p,n-i))
    6 memorized-CUT-ROD[n] = q

  • 自底向上

    需要恰当定义子问题的“规模”,使得任何子问题的求解都只依赖于“更小的”子问题,进而将子问题按规律排序,按由小到大的顺序进行求解,当求解某个自问题时,它所以来的子问题都已经求解完毕。

    伪代码略,直接上代码:

    int cut_rod(vector<int> p,int n){
    int len = p.size();
    vector<int> maxvalue(len,0);
    for(int i = 0;i < n;i++){//i=n-1
    maxvalue[i] = p[i];
    for(int j = 1; j <= (i+1)/2;j++){
    maxvalue[i] = max(maxvalue[i],maxvalue[j-1]+maxvalue[i-j]);
    }
    }
    return maxvalue[n-1];
    }

    至此,可以求出该问题的最优解了~

重构解

​ 上面的求解过程可以求出最优解的值,但并没有返回解本身(具体的切割方案),为了得到最优解,需要在求解最优解的同时,保存切割信息。扩展上面的算法,使之对子问题不仅保存最优收益值$r_j$,还保存该最优方案对应的第一段钢条的切割长度,也就是第一段钢条的切割位置距离钢条左端的长度$s_j$,最后输出最优方案时,根据$s_j$即可复原出最优解。

int cut_rod(vector<int> p,int n){
int len = p.size();
vector<int> maxvalue(len,0);//记录最优方案值
vector<int> leftlen(len,0);//记录第一段钢条距左端距离
for(int i = 0;i < n;i++){//i=n-1
maxvalue[i] = p[i];
leftlen[i] = i+1;
for(int j = 1; j <= (i+1)/2;j++){
if(maxvalue[j-1]+maxvalue[i-j]>maxvalue[i]){
maxvalue[i] = maxvalue[j-1]+maxvalue[i-j];
leftlen[i] = j;
}
}
}
//输出最优解方案
int m = n-1;
while(m>=0){
cout<<leftlen[m]<<"\t";
m -= leftlen[m];
}
return maxvalue[n-1];
}

结果如图: