一.算法总体思想
1.总体思想：
将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是独立的，使用分治法求解时，有些子问题被重复计算了许多次。
2.如何改进子问题被重复计算？
如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，就可以避免大量重复计算。
3.动态规划的基本步骤：
1）找出最优解性质，并刻画起结构特征。（寻找最优解的子问题结构）
2）递归的定义最优值（根据子问题结构建立问题的递归解式）
3）自底向上的方式计算出最优值（动态规划思想）
4）根据计算最优值时得到的信息，构造最优解。
二.动态规划例子
1.权重化的活动安排问题
问题描述：
有n个活动，活动j在时刻开始，时刻结束，活动j具有价值,如果两个活动不重叠，则这两个活动是可以兼容的，目标是，在确定的时间段内，找到具有最大价值且相互兼容的活动子集。
1.1 问题分析：
将活动按照结束时间从小到大进行排序
定义p(j)=最接近活动j并且与活动j兼容的活动序号i，i 定义OPT（j）=j个活动（1，2，...,j）所获得的最大价值，即：最优解 1.2 最优子结构与子问题分析： 情况1：OPT（j）中包含第j个活动 必定包含由1，2，...,p(j)个活动构成的最优解 情况2:OPT（j）没有选择第j个活动 必定包含活动1，2，...,j-1个活动所构成的最优解 2.多个矩阵连乘模块设计 2.1 引理： 对于一个q*p矩阵A和一个p*r矩阵B，AB需要多少次标准乘法计算？ 答案是：q*p*r 2.2 问题描述： 给定n个矩阵，其中与是可乘的（i=1，2，...,n-1），考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号。 2.3 问题分析： 将矩阵连乘积简记为A[i:j]，这里; 考察计算A[i:j]的最优计算次序。 设这个计算次序在矩阵和之间将矩阵链断开，。 则其相应完全加括号的方式为 总计算量=A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。 特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解，所以具有最优子结构性质。 2.4 建立递推关系式： 设计算A[i:j],,所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] 当i=j时，m[i,j]=0; 当i 可以递归的定义m[i,j]为： k的位置只有j-1种可能 使用动态规划解决此问题，可以根据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案，每个子问题只计算一次，而在后面需要的时候简单的查一下，从而避免了大量的计算。 对于m[i][j]数组，只需要填入上三角中的元素即可（因为i<=j）。 每次按照对角线的方式去填写m[i][j]数组中的元素，首先将主对角线中的元素全部置为0，相当于初始化的作用。 2.5 算法时间复杂度： 3. 0-1背包问题 3.1 问题描述： 给定n中物品和一个背包，物品i的重量>0,其价值,背包容量为C。 应如何选择装入背包的物品，使得装入背包中物品的总价值最大且总重量不超过C？ 装入方法： 每种物品只有两种选择，即装入背包或不装入。不能将物品多次装入或部分装入。 问题可以进一步抽象为：找出n元向量，满足约束条件下的最优化问题。 求： 约束条件为： 3.2 分析子问题结构： 假设是一个最优解，则是下面相应子问题的一个最优解 分析过程1: 定义OPT(n)=由1,...,n个物体装填背包所产生的最大价值 case 1:OPT不选择第n个物体 OPT为{1,2,...,n-1}个物体装填背包所产生的最大价值 case 2:OPT选择第n个物体进行装填 接收物体n并不意味着我们必须拒绝其他物体 在不知道其他哪些物体已经在n前被选择的情况下，我们也并不能知道是否有足够的空间能容纳物体n 证明： 用反证法证明 若不然，设是子问题的一个最优解，而不是最优解，由此可知： 且 因此 这说明是所给0-1背包问题的更优解，从而不是问题的最优解。 分析过程2: 添加一个变量j 定义m(i,j)=背包容量为j，由1,...,i个物体装填背包问题的最优值。 case 1:m(i,j)不选择第i个物体 m(i,j)为{1,...,i-1}个物体装填背包所产生的最大价值，当重量限制为j case 2:m(i,j)选择第i个物体 新的重量限制= m(i,j)为新重量限制下，{1,...i-1}个物体装填背包所产生的最大价值 递推关系式如下： 3.3 代码实现： void knapsack(int v[],int w[],int c,int n){//v表示价值，w表示重量，c表示背包容量,n表示物品种类 int m[MAX_SIZE][MAX_SIZE]={0};//m[i,j]=背包容量为j，由1,...,i个物体装填背包问题的最优值 int i,j; for(j=0;j<=c;j++){//0个物体时 m[0][j]=0; } for(i=0;i for(j=1;j<=c;j++){//重量从1到c if(w[i]>j){ m[i][j]=m[i-1][j]; } else{ m[i][j]=max(m[i-1][j],v[i]+m[i-1][j]); } } } } 时间复杂度： 4.最长公共子序列问题： 4.1 问题描述： 给定两个字符序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。找到两个序列的最长公共子序列。 若给定序列，则另一序列，是X的子序列是指:存在一个严格递增下标序列使得对于所有，有： 例如，序列是序列的子序列，相应的递增下标序列为{2,3,5,7} 4.2 问题分析： 设序列，的最长公共子序列为 1） 若,则，且是和的最长公共子序列。 2）若,则Z是和Y的最长公共子序列。 3）若,则Z是和X的最长公共子序列。 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。 设c[i][j]表示序列X和序列Y的最长公共子序列的长度。 建立递推式如下： int LCS(char x[],char y[],int len1,int len2,int a[],int b[]){ int i,j,k; int c[MAX_SIZE][MAX_SIZE]={0}; for(i=0;i c[i][0]=0; } for(i=0;i c[0][i]=0; } for(i=1;i for(j=1;j if(x[i]==y[j]){ c[i][j]=c[i-1][j-1]+1; a[i]=1; b[i]=1; } else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; } else{ c[i][j]=c[i][j-1]; } } } return c[len1-1][len2-1]; } 推荐阅读
发表评论