前言:动态规划的概念
动态规划(dynamic programming)是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分为一些独立的子问题,递归的求解各个问题,然后合并子问题的解而得到原问题的解。例如归并排序,快速排序都是采用分治算法思想。本书在第二章介绍归并排序时,详细介绍了分治算法的操作步骤,详细的内容请参考:http://www.cnblogs.com/Anker/archive/2013/01/22/2871042.html。而动态规划与此不同,适用于子问题不是独立的情况,也就是说各个子问题包含有公共的子问题。如在这种情况下,用分治算法则会重复做不必要的工作。采用动态规划算法对每个子问题只求解一次,将其结果存放到一张表中,以供后面的子问题参考,从而避免每次遇到各个子问题时重新计算答案。
动态规划与分治法之间的区别:
(1)分治法是指将问题分成一些独立的子问题,递归的求解各子问题
(2)动态规划适用于这些子问题不是独立的情况,也就是各子问题包含公共子问题
动态规划通常用于最优化问题(此类问题一般有很多可行解,我们希望从这些解中找出一个具有最优(最大或最小)值的解)。动态规划算法的设计分为以下四个步骤:
(1)描述最优解的结构
(2)递归定义最优解的值
(3)按自低向上的方式计算最优解的值
(4)由计算出的结果构造一个最优解
动态规划最重要的就是要找出最优解的子结构。
一 钢条切割
钢条切割问题描述:给定一段长度为n英寸的钢条和一个价格表Pi(i=1,2,3,...,n),求切割钢铁方案,使得销售收益rn最大。注意,如果长度为n英寸的钢条的价格Pn足够大,最优解可能就是完全不需要切割。
假设一个最优解将钢条切割为k段(对某个1<=k<=n),那么最优切割方案
n=i1+i2+...+ik
将钢条切割的长度分别为i1,i2,...ik的小段,得到的最大收益
rn=pi1+pi2+...+pik
更一般地,对于rn(n>=1),我们可以用更短的最优切割收益来描述它:
rn=max(pn,r1+r(n-1),r2+r(n-2),...,r(n-1)+r1)
第一个参数pn对应不切割,直接出售长度为n英寸的钢条的方案。其他n-1个参数对应另外n-1种方案:对每个i=1,2,...n-1,首先将钢条切割为长度为i和n-i的两端,接着求解这两段的最优切割收益ri和r(n-i)(每种方案的最优收益为两段的最优收益之和)。由于无法预知哪种方案会获得最大收益,我们必须考察所有可能的i,选取其中收益最大者。如果直接出售原钢条会获得最大收益,我们当然可以选择不做任何切割。
自顶向下递归实现
下面是一种直接的自顶向下的递归方法。
CUT-ROD(p,n) if n==0 return 0 q=-∞ for i=1 to n q=max(q,p[i]+CUT-ROD(p,n-i)) return q
C++实现代码:
#include<iostream> using namespace std; int cut_rod(int p[],int n) { if(n==1) return 0; int q=-1; int i; for(i=1;i<n;i++) q=max(q,p[i]+cut_rod(p,n-i)); return q; } int main() { int p[11]={0,1,5,8,9,10,17,17,20,24,30}; int i; for(i=0;i<11;i++) cout<<cut_rod(p,i+1)<<endl; }
运行结果:
使用动态规划方法求解最优钢条切割问题
动态规划有两种等价的实现方法,下面以钢条切割问题为例展示这两种方法。
第一种方法称为带备忘的自顶向下法。此方法仍按自然的递归形式编写过程,但过程会保存每个子问题的解(通常保存在一个数组或散列表中)。当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间;否则,按通常方式计算这个子问题。我们称这个递归过程是带备忘的,因为它“记住”了之前已经计算出的结果。
第二种方法称为自底向上法。这种方法一般需要恰当定义子问题“规模”的概念,使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序,按由小到大的顺序进行求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已经保存。每个子问题只需求解一次,当我们求解它(也是第一次遇到它)时,它的所有前提子问题都已经求解完成。
下面给出的是自顶向下CUT-ROD过程的伪代码,加入了备忘机制:
MEMOIZED-CUT-ROD(p,n) let r[0...n] be a new array for i=0 to n r[i]=-∞ return MEMOIZED-CUT-ROD-AUX(p,n,r) MEMOIZED-CUT-ROD-AUX(p,n,r) if r[n]>=0 return r[i] if n==0 q=0 else q=-∞ for i=1 to n q=max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r)) r[n]=q return q
自底向上版本:
BOTTOM-UP-CUT-ROD(p,n) let r[0..n] be a new array r[0]=0 for j=1 to n q=-∞ for i=1 to j q=max(q,p[i]+r[j-i]) r[j]=q return r[n]
C++代码:
#include<iostream> using namespace std; int cut_rod(int p[],int n) { if(n==0) return 0; int q=-1; int i; for(i=1;i<=n;i++) q=max(q,p[i]+cut_rod(p,n-i)); return q; } //自顶向下 int memoized_cut_rod_aux(int p[],int n,int r[]) { int q=-1; int i; if(r[n]>=0) return r[n]; if(n==0) return 0; for(i=1;i<=n;i++) q=max(q,p[i]+memoized_cut_rod_aux(p,n-i,r)); r[n]=q; return q; } int memoized_cut_rod(int p[],int n) { int i; int r[n]; for(i=0;i<=n;i++) r[i]=-1; return memoized_cut_rod_aux(p,n,r); } //自底向上 int cutrod(int p[],int n) { int r[n]; int i,j; for(i=0;i<=n;i++) r[i]=0; int q; for(j=1;j<=n;j++) { q=-1; for(i=1;i<=j;i++) q=max(q,p[i]+r[j-i]); r[j]=q; } return r[n]; } int main() { int p[11]={0,1,5,8,9,10,17,17,20,24,30}; int i; cout<<"递归:"<<endl; for(i=0;i<11;i++) cout<<cut_rod(p,i)<<endl; cout<<"自顶向下:"<<endl; for(i=0;i<11;i++) { cout<<memoized_cut_rod(p,i)<<endl; } cout<<"自底向上:"<<endl; for(i=0;i<11;i++) { cout<<cutrod(p,i)<<endl; } }
运行结果: