算法——动态规划_完全加括号是什么意思
赞
踩
基本概念
思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
实际应用中，很多问题经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
基本要素
最优子结构
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
重叠性质
子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
基本步骤
1.找出最优解的性质，并刻划其结构特征。
2.递归地定义最优值。
3.以自底向上的方式计算出最优值。
4.根据计算最优值时得到的信息，构造最优解。
动态规划算法和备忘录法
备忘录方法是动态规划算法的变形，它通过分治思想对原问题进行分解，以存储子问题的解的方式解决冗余计算，并采用自顶向下的递归方式获取问题的最终解。
与动态规划算法的不同之处是动态规划算法的递归方式是自底向上递归求解，而备忘录方法的递归方式是自顶向下递归求解。
当一个问题的所有子问题都至少要解一次时，使用动态规划算法。
当子问题空间中的部分子问题不需要求解时，使用备忘录方法。
具体例子
矩阵连乘问题
题目描述：
给定n个矩阵｛A1,A2,…,An｝，其中，Ai与Ai+1是可乘的，(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的次数最小
问题分析：
- 矩阵连乘的条件：第一个矩阵的列等于第二个矩阵的行，此时两个矩阵是可乘的；
- 多个矩阵连乘的结果矩阵，其行列等于第一个矩阵的行和最后一个矩阵的列；
- 两个矩阵相乘的计算量；
抽象描述：
完全加括号的矩阵连乘积可递归地定义为：
1）单个矩阵是完全加括号的；
2）矩阵连乘积A 是完全加括号的，则A可
表示为2个完全加括号的矩阵连乘积B和C
的乘积并加括号，即A=(BC)
3）输入：向量 P = < P0, P1, … , Pn >， 其中 P0, P1, …, Pn为 n 个矩阵的行数与列数
4）输出：矩阵链乘法加括号的位置.
矩阵A： i 行 j 列，B: j 行 k 列，以元素相乘作基本运算,计算 AB的工作量
AB: i 行 k列，计算每个元素需要做 j 次乘法, 总计乘法次数 为 i j k
算法：
特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
假设
m[i,j]：计算A[i:j]所需要的最少数乘次数，
m[1,n]：原问题的最优值
（A1…Ak)(Ak+1…An)是最优解
最优解（A1…Ak)(Ak+1…An)的代价方程：
m[i][i]=0 计算A[i:i]的最小乘法数 Ai的维数是Pi-1×Pi
m[i][j]=m[i][k]+m[k+1][j]+Pi-1PkPj
最优值的代价方程
例子
对于一组矩阵:
A1(30x35),A2(35x15),A3(15x5),A4(5x10),A5(10x20),A6(20x25) 个数N为6，那么p数组保存它们的行数和列数：p={30,35,15,5,10,20,25}共有N+1即7个元素，p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数…p[5],p[6]代表第六个矩阵的行数和列数
s[i][j]为k值，具体在哪里分割
代码
void MatrixChain(int *p，int n，int **m，int **s)
{
//初始化
for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++)
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
//自底向上计算每一个m[i][j]的值，并将结果填入表中
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}
}
}
}
//构造最优解
void TraceBack(int i, int j, int **S)
{
if (i==j)
break;
TraceBack(i,s[i][j],s);
TraceBack(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<s[i][j]+1<<","<<j<<endl;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
最大字段和
问题定义
给定n个数(可以为负数)的序列 (a1, a2, … , an)求
例如 (-2, 11, -4, 13, -5, -2)
解：最大子段和为 a2+a3+a4=20
一列全是负数，最大字段和为0
算法分析：
算法1：对所有的 ( i, j )对，顺序求和 ai + … + aj 并比较出最大的和
算法2：分治策略，将数组分成左右两半，分别计算左边的最大和、右边的最 大和、跨边界的最大和，然后比较其中最大者
算法3：动态规划
算法复杂度为O(n)。
动态规划算法设计要点：
(划分)多阶段决策过程，每步处理一个子问题，界定子问题的边界(初值问题)。
(2) 列出优化函数的递推方程及初值(无比关键)。
(3) 问题要满足优化原则或者最优子结构性质。即：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。
实现
int MaxSum(int n, int *a, int *c, int *d)
{ int *b, sum; sum=0; b[0]=0;
for(i=1; i<=n; i++)
{ if(b[i-1]>0)
{ b[i]=b[i-1]+a[i]; c[i]=1;}
else {b[i]=a[i]; c[i]=0;}
if(b[i]>sum) {sum=b[i]; (*d)=i;}
}
return sum;
}
//构造最优解
void output(int *c, int d)
{ int i=d;
do
{ if(i==d)
printf("=%d",a[i]);
else
printf("+%d",a[i]);
}while(c[i--]==1);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
最长公共子序列
问题的定义：
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xi。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
注意子序列和字串的区别
问题的分析：
1.子问题间的依赖关系
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则
(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。
(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。
(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。
满足优化原则和子问题重叠性
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
void LCSLength(int m，int n，char *x，char *y，int **c，int **b)
{
int i，j;
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; }
}
}
void LCS(int i，int j，char *x，int **b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
完整代码
#include<bits/stdc++.h>
using namespace std;
string X ;
string Y ;
vector<vector<int> > c; // 动态规划表
set<string> lcs; // set保存所有的LCS
int lcs_length(int m, int n)
{
// 表的大小为(m+1)*(n+1)
c = vector<vector<int> >(m+1,vector<int>(n+1));
for(int i=0; i<m+1; ++i)
{
for(int j=0; j<n+1; ++j)
{
// 第一行和第一列置0
if (i == 0 || j == 0)
c[i][j] = 0;
else if(X[i-1] == Y[j-1])
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
}
return c[m][n];
}
void lcs_print(int i, int j, string lcs_str)
{
while (i>0 && j>0)
{
if (X[i-1] == Y[j-1])
{
lcs_str.push_back(X[i-1]);
// cout<<X[i-1]<<endl;
--i;
--j;
}
else
{
if (c[i-1][j] > c[i][j-1])
--i;
else if (c[i-1][j] < c[i][j-1])
--j;
else
{
lcs_print(i-1, j, lcs_str);
lcs_print(i, j-1, lcs_str);
return;
}
}
}
// cout<<lcs_str<<endl;
reverse(lcs_str.begin(),lcs_str.end());
lcs.insert(lcs_str);
}
int main()
{
int m;
int n;
cin>>m>>n;
cin>>X>>Y;
int length = lcs_length(m, n);
string str;
lcs_print(m, n, str);
set<string>::iterator it = lcs.begin();
for( ; it!=lcs.end(); it++)
cout << *it << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
凸多边形最优三角剖分问题
问题定义：
用多边形顶点的逆时针序列表示凸多边形，即
P={v0,v1,…,vn-1}表示具有n条边的凸多边形。
若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。
给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
问题的分析：
三角剖分的结构及其相关问题：
一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。
凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。
矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i<j，对应于矩阵连乘积A[i+1:j]。
算法描述和递归结构：
定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。
t[i][j]的值可以利用最优子结构性质递归地计算。当j-i≥1时，凸子多边形至少有3个顶点。由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置。由此，t[i][j]可递归地定义为：
自底向上计算最优值
void MinWeight(int n, int **t, int **s)
{ for(i=1; i<=n; i++) t[i][i]=0;
for(r=2; r<=n; r++)
for(i=1; i<=n-r+1; i++)
{ j=i+r-1;
t[i][j]=t[i][i]+t[i+1][j]+w(i-1,i, j);
s[i][j]=i;
for(k=i+1; k<j; k++)
{ tmp=t[i][k]+t[k+1][j]+w(i-1, k, j);
if(tmp<t[i][j]) {t[i][j]=tmp; s[i][j]=k;}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
0-1背包问题
问题定义：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
0-1背包问题是一个特殊的整数规划问题。
算法描述：
设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。
实例
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
只要能通过找规律手工填写出上面这张表就算理解了0-1背包的动态规划算法。
首先要明确这张表是至底向上，从左到右生成的。
为了叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不了。
对于d2单元格，表示只有物品e，d时,承重为2的背包,所能装入的最大价值，仍然是0，因为物品e,d都不是这个背包能装的。同理，c2=0，b2=3,a2=6。
对于承重为8的背包，a8=15,是怎么得出的呢？
一个是f[i+1,j],对于这个例子来说就是b8的值9，另一个是f[i+1,j-Wi]+Pi；
在这里，f[i+1,j]表示有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值。
f[i+1,j-Wi]表示有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值。
f[i+1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6
由于f[i+1,j-Wi]+Pi = 9 + 6 = 15 大于f[i+1,j] = 9，所以物品a应该放入承重为8的背包
