最长公共子序列和最长公共子串是有区别的,之前我一直把它们混淆。
- 最长公共子串举例:假设S1={A,D,C,B,E,X,Q},S2={H,P,D,C,B,E,M,L} 那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。 最长公共子序列。
- 最长公共子序列举例:假设S1={A,B,C,A,D,A,B},S2={B,A,C,D,B,A},那么它们的LCS就是{B,A,D,B}。
这是一个动态规划问题。如何求解最长公共子序列(以下用LCS代替)呢?我们假设已经知道Z={z1,z2,...zk}是X={x1,x2,...,xm}和Y={y1,y2,...,yn}的LCS,那么可以分以下三种情况讨论(具体每种情况证明不再累述):
- xm=yn=zk:那么Zk-1是Xm-1和Yn-1的LCS。
- xm≠yn,yn≠zk:我们可以把yn去掉,那么Zk是Xm和Yn-1的LCS。
- xm≠yn,xm≠zk:我们可以把xm去掉,那么Zk是Xm-1和Yn的LCS。
基于以上情况,我们可以得到LCS递归式。我们假设c[i][j]表示Xi和Yi的LCS长度,那么:
- c[i][j]=0(i=0或j=0);
- c[i][j]=c[i-1]c[j-1]+1(i,j>0且xi=yi);
- c[i][j]=max{c[i-1][j],c[i],[j-1]};(i,j>0且xi≠yi)。
这样我们就可以得到LCS的长度。如何得到具体内容是什么呢?我们可以借用一个辅助数组b[i][j],这个数组用来记录c[i][j]的来源,分别有如下情况:
- c[i][j]=c[i-1][j-1]+1,则b[i][j]=1;
- c[i][j]=c[i][j-1],则b[i][j]=2;
- c[i][j]=c[i-1][j],则b[i][j]=3。
这样就可以根据b[m][n]反向追踪LCS,当b[i][j]=1,输出xi;当b[i][j]=2,追踪c[i][j-1];当b[i][j]=3,追踪c[i-1][j],直到i=0或j=0停止。
(1)初始化。初始化c[][]第1行和第1列为0。 (2)开始操作。具体是将s1[i]分别与s2[j-1](j=1,2,...,len2)进行比较,若字符相等c[i][j]=左上角数值+1,且b[i][j]=1;若不相等,则c[i][j]等于左侧或者上侧重最大的一个数值,若左侧和上侧相等,则取左侧,且b[i][j]=2或3(当取左侧为2,取上侧为3)。最后的c[][]和b[][]如下所示: 下表是c[][]:
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | |
A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
A | 0 | 1 | 2 | 2 | 2 | 2 | 3 |
D | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
下表是b[][]:
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | |
1 | 0 | 2 | 1 | 2 | 2 | 2 | 1 |
2 | 0 | 1 | 2 | 2 | 2 | 1 | 2 |
3 | 0 | 3 | 2 | 1 | 2 | 2 | 2 |
4 | 0 | 3 | 1 | 2 | 2 | 2 | 1 |
5 | 0 | 3 | 3 | 2 | 1 | 2 | 2 |
6 | 0 | 3 | 1 | 2 | 3 | 2 | 1 |
7 | 0 | 1 | 3 | 2 | 3 | 1 | 2 |
根据c[][]可以得出,LCS的长度为4(也就是c[][]最后一个值)。然后开始判断内容是什么,这是要根据b[][]来。 首先,b[7][6]=2,向左找b[7][5]=1,所以向左上角找b[6][4],得到字母为s1[6]=[B]; b[6][4]=3,向上找b[5][4]=1,向左上角找b[4][3],得到字母s1[4]=[D]; b[4][3]=2,向左找b[4][2=1,向左上角找b[3][1],得到字母s1[3]=[A]; b[3][1]=3,向上找b[2][1]=1,向左上角找b[1][0],得到字母s1[1]=[B]. 由于b[1][0]=0,所以算法停止,返回结果为“BADB”。
void LCSL()
{
int i, j;
for(i=1;i<len1;i++)
for (j = 1; j < len2; j++)
{
if (s1[i - 1] == s2[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else
{
if (c[i][j - 1] >= c[i - 1][j])
{
c[i][j] = c[i][j - 1];
b[i][j] = 2;
}
else
{
c[i][j] = c[i - 1][j];
b[i][j] = 3;
}
}
}
}
void print(int i, int j)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == 1)
{
print(i - 1, j - 1);
cout << s1[i - 1];
}
else if (b[i][j] == 2)
print(i, j - 1);
else
print(i - 1, j);
}
- 编辑距离的d[][]取值公式如下: (一个前提,若xi=yj,则diff=0;否则为1) d[i][j]=min{d[i - 1][j] + 1, d[i][j - 1] + 1,d[i-1][j-1]+diff}
- 构造最优解:编辑距离是从右下角开始,逆向查找d[i][j]的来源:上面表示需要删除,左侧表示需要插入;左上角要判断字符是否相等,若相等,不做任何操作,若不相等,执行替换。
- 两者的时间复杂度都是O(n*m)。
int min(int a, int b,int c)
{
int temp = (a < b) ? a : b;
return (temp < c) ? temp : c;
}
//编辑距离函数
int editdistance(char *str1, char *str2)
{
int i, j;
int len1 = strlen(str1);
int len2 = strlen(str2);
for (i = 0; i <= len1; i++)
{
d[i][0] = i;
}
for (j = 0; j <= len2; j++)
{
d[0][j] = j;
}
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
{
int diff;
if (str1[i - 1] == str2[j - 1])
diff = 0;
else
diff = 1;
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1,d[i-1][j-1]+diff);
}
}
return d[len1][len2];
}
假设在一条河上有n个游艇出租站,游客可以在这些游艇出租站租游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到j之间的租金为r(i,j),i<=i<=j<=n。设计一个算法,计算从游艇出租站i到出租站j所需要的租金最少。
(1)分析最优解的结构特征 (2)简历最优值的递归式 m[i][j]= 0(j=i); r[i][j];j=i+1; min{m[i][k]+m[k][j],r[i][j],j>i+1。
(1)确定合适的数据结构:采用二维数组r[][]输入数据,二维数组m[][]存放各个子问题的最优值,二维数组s[][]存放各个子问题的最优决策(停靠站点)。 (2)初始化:m[i][j]=r[i][j],然后再找有没有比m[i][j]小的值,如果有,则记录该最优值和最优解即可,s[i][j]=0. (3)循环阶段:
- 按照递归关系式计算3个站点i,i+1,j(j=i+2)的最优值,并将其存入m[i][j],同时将最优策略存入s[i][j],i=1,2,...,n-2。
- 按照递归关系式计算4个站点i,i+1,i+2,j(j=i+3)的最优值,并将其存入m[i][j],同时将最优策略存入s[i][j],i=1,2,...,n-3。
- 以此类推,直到求出n个站点的最优值m[1][n]。
(4)构造最优解。根据s[][]递归构造最优解。s[1][n]是第一个站点到底n个站点)1,2,...,n)的最优解的停靠站点,即停靠了第s[1][n]个站点,我们在递归构造两个子问题(1,2,...,k)和(k,k+1,...,n)的最优解停靠站点,一直递归到只包含一个站点为止。
void rent()
{
int i, j, k, d;
for (d = 3; d <= n; d++)
{
for (i = 1; i <= n - d + 1; i++)
{
j = i + d - 1;
for (k = i + 1; k < j; k++)
{
int temp;
temp = m[i][k] + m[k][j];
if (temp < m[i][j])
{
m[i][j] = temp;
s[i][j] = k;
}
}
}
}
}
void print(int i, int j)
{
if (s[i][j] == 0)
{
cout << "-- " << j;
return;
}
print(i, s[i][j]);
print(s[i][j], j);
}
其实只是把总结的递归式中的j>i+1的时候的min改为了max。所以只是修改了代码中的
if (temp < m[i][j])
将其改为了
if (temp > m[i][j])
最优递归式: 当i=j时,只有一个矩阵,m[i][j]=0; 当i<j的时候,m[i][j]=min{m[i][k]+m[k+1][j]+pip(k+1)qj}
(1)确定合适的数据结构。用一维数组p[]记录矩阵的行和列,第i个矩阵的行数存在数组的第i-1位置,列存在第i位置。二维数组m[][]用来存放各个子问题的最优值,二维数组s[][]来存放各个子问题的最优决策(加括号的位置)。 (2)初始化。m[i][i]=0,s[i][i]=0。 (3)循环阶段。
- 按照递归关系式计算2个矩阵Ai、Ai+1相乘时的最优值,j+i+1,并将其存入m[i][j];同时将最优策略计入s[i][j]。i=1,2,3,..,n-1。
- 按照递归关系式计算3个矩阵相乘Ai、Ai+1、Ai+2,相乘时的最优值,j+i+2,并将其存入m[i][j],同时将最优策略记入s[i][j],i=1,2,3,...,n-2。
- 以此类推,直到求出n个矩阵相乘的最优值m[1][n]。
(4)构造最优解 根据最有决策信息数组s[][]递归构造最优解。s[1][n]表示A1A2...An最优解的加括号位置,我们在递归构造两个子问题的最优解加括号位置,一直低轨道子问题只包含一个矩阵为止。
矩阵 | A1 | A2 | A3 | A4 | A5 |
---|---|---|---|---|---|
规模 | 3*5 | 5*10 | 10*8 | 8*2 | 2*4 |
(1)初始化 m[i][i]=0,s[i][i]=0 (2)计算两个矩阵相乘的最优值 m[][]如下:
m[][] | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 150 | 390 | 290 | 314 |
2 | 0 | 400 | 260 | 300 | |
3 | 0 | 160 | 240 | ||
4 | 0 | 64 | |||
5 | 0 |
s[][]如下:
s[][] | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 1 | 2 | 1 | 4 |
2 | 0 | 2 | 2 | 4 | |
3 | 0 | 3 | 4 | ||
4 | 0 | 4 | |||
5 | 0 |
(3)构造最优解 类似于游艇租赁
void matrixchain()
{
int i,j,r,k;
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
for(r = 2; r <= n; r++) //不同规模的子问题
{
for(i = 1; i <= n-r+1; i++)
{
j = i + r - 1;
m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j]; //决策为k=i的乘法次数
s[i][j] = i; //子问题的最优策略是i;
for(k = i+1; k < j; k++) //对从i到j的所有决策,求最优值,记录最优策略
{
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 print(int i,int j)
{
if( i == j )
{
cout <<"A[" << i << "]";
return ;
}
cout << "(";
print(i,s[i][j]);
print(s[i][j]+1,j);
cout << ")";
}
不同点就在于递归公式的不同,最优三角剖分的递归公式如下: 当i=j的时候,m[i][j]=0; 当i<j的时候,m[i][j]=min{m[i][k]+m[k+1][j]+w(v(i-1)vkvj)}
我们以一个凸多边形为例,其每条边的权重如下表所示
g[][] | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 2 | 3 | 1 | 5 | 6 |
1 | 2 | 0 | 3 | 4 | 8 | 6 |
2 | 3 | 3 | 0 | 10 | 13 | 7 |
3 | 1 | 4 | 10 | 0 | 12 | 5 |
4 | 5 | 8 | 13 | 12 | 0 | 3 |
5 | 6 | 6 | 7 | 5 | 3 | 0 |
(1)初始化:令m[i][i]=0,s[i][i]=0 (2)计算赋值如下:
m[][] | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 8 | 22 | 40 | 54 |
2 | 0 | 17 | 41 | 52 | |
3 | 0 | 35 | 42 | ||
4 | 0 | 20 | |||
5 | 0 |
s[][] | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
1 | 0 | 1 | 2 | 3 | 3 |
2 | 0 | 2 | 3 | 3 | |
3 | 0 | 3 | 3 | ||
4 | 0 | 4 | |||
5 | 0 |
所以最优权值为m[1][5]=54 (3)构造最优解。过程与矩阵快速相乘类似,都是根据s[][]对应的位置来分成子问题,所以首先是看到s[1][5]=3,所以分为了v0~ v3 和 v3~v5。
- 因为v0~v3中有结点,所以子问题1不为空,输出该弦v0v3;同理,输出v3v5。
- 对于子问题1进行递归,读取s[1][3]=2,因为v0~v2有结点,所以输出v0v2……
- 最后输出的最优解为v0v3,v3v5,v0v2。
void Convexpolygontriangulation()
{
for(int i = 1 ;i <= n ; i++) // 初始化
{
m[i][i] = 0 ;
s[i][i] = 0 ;
}
for(int d = 2 ;d <= n ; d++) // 枚举点的个数
for(int i = 1 ;i <= n - d + 1 ; i++) // 枚举起始点
{
int j = i + d - 1 ; // 终点
m[i][j] = m[i+1][j] + g[i-1][i] + g[i][j] + g[i-1][j] ;
s[i][j] = i ;
for(int k = i + 1 ;k < j ; k++) // 枚举中间点
{
double temp = m[i][k] + m[k+1][j] + g[i-1][k] + g[k][j] + g[i-1][j] ;
if(m[i][j] > temp)
{
m[i][j] = temp ; // 更新最优值
s[i][j] = k ; // 记录中间点
}
}
}
}
void print(int i , int j) // 输出所有的弦
{
if(i == j) return ;
if(s[i][j]>i)
cout<<"{v"<<i-1<<"v"<<s[i][j]<<"}"<<endl;
if(j>s[i][j]+1)
cout<<"{v"<<s[i][j]<<"v"<<j<<"}"<<endl;
print(i ,s[i][j]);
print(s[i][j]+1 ,j);
//cout<<"{ v"<<i-1<<" , v"<<s[i][j]<<" , v"<<j<<" }"<<endl; //输出所有剖分后的三角形
}
设Min[i][j]代表从第i堆石子到第j堆石子合并的最小花费,Min[i][k]代表从第i堆石子到底k堆石子合并的最小花费,Min[k+1][j]代表从第k+1堆石子到第j堆石子合并的最小花费。那么递推式如下: Min[i][j]=0,i=j Min[i][j]=min{m[i][k]+m[k+1][j]+w(i,j)} i<j 同理,设Max[i][j]代表从第i堆石子到第j堆石子合并的最大花费,Max[i][k]代表从第i堆石子到底k堆石子合并的最大花费,Max[k+1][j]代表从第k+1堆石子到第j堆石子合并的最大花费。那么递推式如下: Max[i][j]=0,i=j Max[i][j]=max{m[i][k]+m[k+1][j]+w(i,j)} i<j
void straight(int a[],int n)
{
for(int i=1;i<=n;i++) // 初始化
Min[i][i]=0, Max[i][i]=0;
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
for(int v=2; v<=n; v++) // 枚举合并的堆数规模
{
for(int i=1; i<=n-v+1; i++) //枚举起始点i
{
int j = i + v-1; //枚举终点j
Min[i][j] = INF; //初始化为最大值
Max[i][j] = -1; //初始化为-1
int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
for(int k=i; k<j; k++) { //枚举中间分隔点
Min[i][j] = min(Min[i][j], Min[i][k] + Min[k+1][j] + tmp);
Max[i][j] = max(Max[i][j], Max[i][k] + Max[k+1][j] + tmp);
}
}
}
}
void Circular(int a[],int n)
{
for(int i=1;i<=n-1;i++)
a[n+i]=a[i];
n=2*n-1;
straight(a, n);
n=(n+1)/2;
min_Circular=Min[1][n];
max_Circular=Max[1][n];
for(int i=2;i<=n;i++)
{
if(Min[i][n+i-1]<min_Circular)
min_Circular=Min[i][n+i-1];
if(Max[i][n+i-1]>max_Circular)
max_Circular=Max[i][n+i-1];
}
}
时间复杂度为O(n3)
最小值可以用四边形不等式来优化。 复杂度为O(n2)
void get_Min(int n)
{
for(int v=2; v<=n; v++) // 枚举合并的堆数规模
{
for(int i=1; i<=n-v+1; i++) //枚举起始点i
{
int j = i + v-1; //枚举终点j
int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
int i1=s[i][j-1]>i?s[i][j-1]:i;
int j1=s[i+1][j]<j?s[i+1][j]:j;
Min[i][j]=Min[i][i1]+Min[i1+1][j];
s[i][j]=i1;
for(int k=i1+1; k<=j1; k++) //枚举中间分隔点
if(Min[i][k]+ Min[k+1][j]<Min[i][j])
{
Min[i][j]=Min[i][k]+Min[k+1][j];
s[i][j]=k;
}
Min[i][j]+=tmp;
}
}
}
void get_Max(int n)
{
for(int v=2; v<=n; v++) // 枚举合并的堆数规模
{
for(int i=1; i<=n-v+1; i++) //枚举起始点i
{
int j = i + v-1; //枚举终点j
Max[i][j] = -1; //初始化为-1
int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
if(Max[i+1][j]>Max[i][j-1])
Max[i][j]=Max[i+1][j]+tmp;
else
Max[i][j]=Max[i][j-1]+tmp;
}
}
}
void straight(int a[],int n)
{
for(int i=1;i<=n;i++) // 初始化
Min[i][i]=0, Max[i][i]=0, s[i][i]=0;
sum[0]=0;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
get_Min(n);
get_Max(n);
}
void Circular(int a[],int n)
{
for(int i=1;i<=n-1;i++)
a[n+i]=a[i];
n=2*n-1;
straight(a, n);
n=(n+1)/2;
min_Circular=Min[1][n];
max_Circular=Max[1][n];
for(int i=2;i<=n;i++)
{
if(Min[i][n+i-1]<min_Circular)
min_Circular=Min[i][n+i-1];
if(Max[i][n+i-1]>max_Circular)
max_Circular=Max[i][n+i-1];
}
}
有n个物品,每个物品的重量为w[i],价值为v[i],购物车容量为W。选若干个物品放入购物车,在不超过容量的前提下使获得的价值最大。
(1)分析最优解的结构特征 (2)建立具有最优值的递归式 可以对每个物品依次检查是否放入或者不放入,对于第i个物品的处理状态:用c[i][j]表示前i件物品放入一个容量为j的购物车可以获得的最大价值。
- 不放入第i件物品,xi=0,装入购物车的价值不增加。那么问题就转化为“前i-1件物品放入容量为j的背包中”,最大价值为c[i-1][j]。
- 放入第i件物品,xi=1,装入购物车的价值增加vi。
那么问题就转化为了“前i-1件物品放入容量为j-w[i]的购物车中”,此时能获得的最大价值就是c[i-1][j-w[i]],再加上放入第i件物品获得的价值v[i]。即c[i-1][j-w[i]]+v[i]。 购物车容量不足,肯定不能放入;购物车容量组,我们要看放入、不放入哪种情况获得的价值更大。 所以,递归函数可以写为: c[i][j]=c[i-1][j](当j<wi); c[i][j]=max{c[i-1][j-w[i]]+v[i],c[i-1][j]}(当j>wi)
(1)确定合适的数据结构 采用一维数组w[i]、v[i]分别记录第i个物品的重量和价值;二维数组用c[i][j]表示前i个物品放入一个容量为j的购物车可以获得的最大价值。 (2)初始化 初始化c[][]数组0行0列为0,其中i=01,2,...,n,j=0,1,2,...,W。 (3)循环阶段
- 按照递归式计算第1个物品的处理情况,得到c[1][j],j=1,2,...,W;
- 按照递归式计算第2个物品的处理情况,得到c[2][j],j=1,2,...,W;
- 以此类推,按照递归式计算第n个物品的处理情况,得到c[n][j],j=1,2,...,W。
(4)构造最优解 c[n][W]就是不超过购物车容量能放入物品的最大价值。如果还想知道具体放入了哪些物品,就需要根据c[][]数组逆向构造最优解,我们可以用一维数组x[i]来存储解向量。
- 首先i=n,j=W,如果c[i][j]>c[i-1][j],则说明第n个物品放入了购物车,令x[n]=1,j-=w[n];如果c[i][j]≤c[i-1][j],则说明第n个物品没有放入购物车,令x[n]=0.
- i--,继续查找答案。
- 直到i=1处理完毕。
假设现在有5个物品,每个物品重量为(2,5,4,2,3),价值为(6,3,5,4,6),购物车容量为10。 c[][]如下表:
c[][] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
2 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 9 | 9 | 9 | 9 |
3 | 0 | 0 | 6 | 6 | 6 | 6 | 11 | 11 | 11 | 11 | 11 |
4 | 0 | 0 | 6 | 6 | 10 | 10 | 11 | 11 | 15 | 15 | 15 |
5 | 0 | 0 | 6 | 6 | 10 | 12 | 12 | 16 | 16 | 17 | 17 |
所以最大价值为c[n][W]=17。 首先读取c[5][10]>c[4][10],说明第5个物品装入了购物车,即x[5]=1,然后j=10-w[5]=10-3=7 然后去c[4][7]; c[4][7]=c[3][7],说明第4个物品没有装入购物车,即x[4]=0; 然后去找c[3][7],依次类推。
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10000
#define M 105
int c[M][maxn];//c[i][j] 表示前i个物品放入容量为j购物车获得的最大价值
int w[M],v[M];//w[i] 表示第i个物品的重量,v[i] 表示第i个物品的价值
int x[M]; //x[i]表示第i个物品是否放入购物车
int main(){
int i,j,n,W;//n表示n个物品,W表示购物车的容量
cout << "请输入物品的个数 n:";
cin >> n;
cout << "请输入购物车的容量W:";
cin >> W;
cout << "请依次输入每个物品的重量w和价值v,用空格分开:";
for(i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(i=1;i<=n;i++)//初始化第0列为0
c[i][0]=0;
for(j=1;j<=W;j++)//初始化第0行为0
c[0][j]=0;
for(i=1;i<= n;i++)//计算c[i][j]
for(j=1;j<=W;j++)
if(j<w[i]) //当物品的重量大于购物车的容量,则不放此物品
c[i][j] = c[i-1][j];
else //否则比较此物品放与不放是否能使得购物车内的价值最大
c[i][j] = max(c[i-1][j],c[i-1][j-w[i]] + v[i]);
cout<<"装入购物车的最大价值为:"<<c[n][W]<<endl;
//用于测试
for (i=1; i<=n; i++ )
{
for (j=1; j<=W; j++ )
cout << c[i][j]<<"\t" ;
cout << endl;
}
cout << endl;
//逆向构造最优解
j=W;
for(i=n;i>0;i--)
if(c[i][j]>c[i-1][j])
{
x[i]=1;
j-=w[i];
}
else
x[i]=0;
cout<<"装入购物车的物品序号为:";
for(i=1;i<=n;i++)
if(x[i]==1)
cout<<i<<" ";
return 0;
}
1.算法复杂度分析 (1)时间复杂度:O(nW) (2)空间复杂度O(nW) 2.算法优化改进 使用一个数组dp[]保证第i次循环结束后dp[j]中表示的就是我们定义的c[i][j]。 所以代码如下:
void opt1(int n,int W)
{
for(i=1;i<=n;i++)
for(j=W;j>0;j--)
if(j>=w[i]) //当物品的重量大于购物车的容量,比较此物品放与不放是否能使得购物车内的价值最大
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
我们可以缩小范围,因为只有当购物车的容量大于等于物品重量的时候才要更新,所以代码如下:
void opt2(int n,int W)
{
for(i=1;i<= n;i++)
for(j=W;j>=w[i];j--)
//当物品的重量大于购物车的容量
//比较此物品放与不放是否能使得购物车内的价值最大
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
我们还可以再缩小范围,确定搜索的下界bound
void opt3(int n,int W)
{
int sum[n];//sum[i]表示从1...i的物品重量之和
sum[0]=0;
for(i=1;i<=n;i++)
sum[i]=sum[i-1]+w[i];
for(i=1;i<=n;i++)
{
int bound=max(w[i],W-(sum[n]-sum[i-1]));
//w[i]与剩余容量取最大值,
//sum[n]-sum[i-1]表示从i...n的物品重量之和
for(j=W;j>=bound;j--)
//当物品的重量大于购物车的容量
//比较此物品放与不放是否能使得购物车内的价值最大
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
递归表达式: c[i][j]=0(j=i-1); c[i][j]=min{c[i][k-1]+c[k+1][j]}+w[i][j](j≥i) w[i][j]=qi-1(j=i-1); w[i][j]=w[i][j-1]+pj+qj
(1)确定合适的数据结构 一维数组:p[]、q[]分别表示实结点和虚结点的搜索概率 二维数组:c[i][j]表示最优二叉搜索树T(i,j)的搜索成本,w[i][j]表示最优二叉搜索树T(i,j)中的所有实结点和虚结点的搜索概率之和,s[i][j]表示最优二叉搜索树T(i,j)的根节点序号。 (2)初始化。c[i][i-1]=0.0,w[i][i-1]=q[i-1],其中i=1,2,3,...,n+1。 (3)循环阶段。
- 按照递归式计算元素规模是1的{si}(j=i)的最优二叉搜索树的搜索成本c[i][j],并记录最优策略,即树根s[i][j],i=1,2,3,..,n。
- 按照递归式计算元素规模是2的{si,si+1}(j=i)的最优二叉搜索树的搜索成本c[i][j],并记录最优策略,即树根s[i][j],i=1,2,3,..,n-1。
- 以此类推,直到求出所有元素{s1,s2,...,sn}的最优二叉搜索树的搜索成本c[1][n]和最优策略s[1][n]。
(4)构造最优解。
- 首先读取s[1][n],令k=s[1][n],输出sk为最优二叉搜索树的根。
- 判断如果k-1<1,表示虚结点ek-1是sk的左子树;否则,递归求解左子树Construct_Optimal_BST(1,k-1,1)。
- 判断如果k≥n,表示虚结点ek是sk的右孩子。;否则,输出s[k+1][n]是sk的右孩子,递归求解右子树Construct_Optimal_BST(k+1,n,1)。
w[][] | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
1 | 0.06 | 0.18 | 0.37 | 0.52 | 0.59 | 0.76 | 1.00 |
2 | 0.08 | 0.27 | 0.42 | 0.49 | 0.66 | 0.90 | |
3 | 0.10 | 0.25 | 0.32 | 0.49 | 0.73 | ||
4 | 0.07 | 0.14 | 0.31 | 0.55 | |||
5 | 0.05 | 0.22 | 0.46 | ||||
6 | 0.05 | 0.29 | |||||
7 | 0.10 |
c[][] | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
1 | 0 | 0.18 | 0.55 | 0.95 | 1.23 | 1.76 | 2.52 |
2 | 0 | 0.27 | 0.67 | 0.90 | 1.38 | 2.09 | |
3 | 0 | 0.25 | 0.46 | 0.94 | 1.48 | ||
4 | 0 | 0.14 | 0.45 | 0.98 | |||
5 | 0 | 0.22 | 0.68 | ||||
6 | 0 | 0.29 | |||||
7 | 0 |
s[][] | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
1 | 1 | 2 | 2 | 2 | 3 | 5 | |
2 | 2 | 2 | 3 | 3 | 5 | ||
3 | 3 | 3 | 3 | 5 | |||
4 | 4 | 5 | 5 | ||||
5 | 5 | 6 | |||||
6 | 6 | ||||||
7 |
void Optimal_BST()
{
for(i=1;i<=n+1;i++)
{
c[i][i-1]=0.0;
w[i][i-1]=q[i-1];
}
for(int t=1;t<=n;t++)//t为关键字的规模
//从下标为i开始的关键字到下标为j的关键字
for(i=1;i<=n-t+1;i++)
{
j=i+t-1;
w[i][j]=w[i][j-1]+p[j]+q[j];
c[i][j]=c[i][i-1]+c[i+1][j];//初始化
s[i][j]=i;//初始化
//选取i+1到j之间的某个下标的关键字作为
//从i到j的根,如果组成的树的期望值当前最小
//则k为从i到j的根节点
for(k=i+1;k<=j;k++)
{
double temp=c[i][k-1]+c[k+1][j];
if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)
//C++中浮点数因为精度问题不可以直接比较
{
c[i][j]=temp;
s[i][j]=k;//k即为从下标i到j的根节点
}
}
c[i][j]+=w[i][j];
}
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
if(flag==0)
{
cout<<"S"<<s[i][j]<<" 是根"<<endl;
flag=1;
}
int k=s[i][j];
//如果左子树是叶子
if(k-1<i)
{
cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
}
//如果左子树不是叶子
else
{
cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
Construct_Optimal_BST(i,k-1,1);
}
//如果右子树是叶子
if(k>=j)
{
cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
}
//如果右子树不是叶子
else
{
cout<<"S"<<s[k+1][j]<<" is the right child of "<<"S"<<k<<endl;
Construct_Optimal_BST(k+1,j,1);
}
}
时间复杂度为O(n3),空间复杂度为O(n2)。 又可以用四边形不等式优化(后续研究一下) 时间复杂度减少到O(n2)。
void Optimal_BST()
{
for(i=1;i<=n+1;i++)
{
c[i][i-1]=0.0;
w[i][i-1]=q[i-1];
}
for(int t=1;t<=n;t++)//t为关键字的规模
//从下标为i开始的关键字到下标为j的关键字
for(i=1;i<=n-t+1;i++)
{
j=i+t-1;
w[i][j]=w[i][j-1]+p[j]+q[j];
int i1=s[i][j-1]>i?s[i][j-1]:i;
int j1=s[i+1][j]<j?s[i+1][j]:j;
c[i][j]=c[i][i1-1]+c[i1+1][j];//初始化
s[i][j]=i1;//初始化
//选取i1+1到j1之间的某个下标的关键字
//作为从i到j的根,如果组成的树的期望值当前
//最小,则k为从i到j的根节点
for(k=i1+1;k<=j1;k++)
{
double temp=c[i][k-1]+c[k+1][j];
if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)
//C++中浮点数因为精度问题不可以直接比较
{
c[i][j]=temp;
s[i][j]=k;//k即为从下标i到j的根节点
}
}
c[i][j]+=w[i][j];
}
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
if(flag==0)
{
cout<<"S"<<s[i][j]<<" 是根"<<endl;
flag=1;
}
int k=s[i][j];
//如果左子树是叶子
if(k-1<i)
{
cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
}
//如果左子树不是叶子
else
{
cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
Construct_Optimal_BST(i,k-1,1);
}
//如果右子树是叶子
if(k>=j)
{
cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
}
//如果右子树不是叶子
else
{
cout<<"S"<<s[k+1][j]<<" is the right child of "<<"S"<<k<<endl;
Construct_Optimal_BST(k+1,j,1);
}
}
动态规划关键总结如下:
- 最优子结构判定
- 做出一个选择。
- 假定已经知道了哪种选择是最优的。
- 最优的会产生哪些子问题。
- 证明原问题的最优解包含其子问题的最优解。
- 如何得到最优解递归式
- 分析原问题最优解和子问题最优解的关系。
- 考察有多少种选择。
- 得到最优解递归式。