1.装配线调度
共有两条装配线,每条有N个装配站,装配线i的第j个装配站装配时间为a[i,j],一个汽车进入装配线i,花费时间e[i],如果在装配站[i,j]之后转移到另外一条线则花费t[i,j].在离开一条线的第N个装配站后,完成的汽车花费时间x[i]离开工厂,待求解的问题是在装配线1选择哪些站,在装配线2选择哪些站使通过总时间最小,时间复杂度O(n)。
#define N 6
int f[3][N+1];//f[i,j]表示从起点到站[i,j]的最快时间,
int l[3][N+1];//l[i,j]为装配线编号,其站j-1被通过[i,j]的最快路线使用
static int lbest,fbest;//装配线lbest的站N被最快路线所使用,fbest为所求最快时间
void fastest_way(int a[3][N+1],int t[3][N],int *e,int *x)
{
int j;
f[1][1]=e[1]+a[1][1];
f[2][1]=e[2]+a[2][1];
for(j=2;j<=N;++j)
{
if(f[1][j-1]+a[1][j]<=f[2][j-1]+t[2][j-1]+a[1][j])
{
f[1][j]=f[1][j-1]+a[1][j];
l[1][j]=1;
}
else
{
f[1][j]=f[2][j-1]+t[2][j-1]+a[1][j];
l[1][j]=2;
}
if(f[2][j-1]+a[2][j]<=f[1][j-1]+t[1][j-1]+a[2][j])
{
f[2][j]=f[2][j-1]+a[2][j];
l[2][j]=2;
}
else
{
f[2][j]=f[1][j-1]+t[1][j-1]+a[2][j];
l[2][j]=1;
}
}
if(f[1][N]+x[1]<=f[2][N]+x[2])
{
fbest=f[1][N]+x[1];
lbest=1;
}
else
{
fbest=f[2][N]+x[2];
lbest=2;
}
}
//构造通过工厂的最快路线
void print_station()
//站号递减的顺序输出装配站
{
int i=lbest;
cout<<"line "<<i<<",statioN "<<N<<endl;
for(int j=N;j>=2;--j)
{
i=l[i][j];
cout<<"line "<<i<<",station "<<j-1<<endl;
}
}
int main()
{
int a[3][7]={{},{0,7,9,3,4,8,4},{0,8,5,6,4,5,7}};
int e[3]={0,2,4};
int t[3][6]={{},{0,2,3,1,3,4},{0,2,1,2,2,1}};
int x[3]={0,3,2};
fastest_way(a,t,e,x);
for(int i=1;i<=6;++i)
cout<<f[1][i]<<" "<<f[2][i]<<" ";
cout<<endl;
for(int j=2;j<=6;++j)
cout<<l[1][j]<<" "<<l[2][j]<<" ";
cout<<endl;
print_station();
return 0;
}
2.矩阵链乘法
给定n个矩阵构成的一个链<A1,A2...An>,矩阵Ai的维数为p[i-1]*p[i],对乘积A1A2...An以一种最小化标量乘法次数的方式进行全部加括号,时间复杂度O(n^3)
#define N 6
#define inf 65535
int m[N+1][N+1];//m[i][j]为计算矩阵Ai..Aj所需标量乘法次数最小值
int s[N+1][N+1];//s[i][j]为使m[i][j]=m[i][k]+m[k+1][j]+p[i-1]p[k]p[j]的k值
void matrix_chain_order(int *p)
{
int i,j;
for(i=1;i<=N;++i)
m[i][i]=0;
for(int l=2;l<=N;++l)
{
for(i=1;i<=N-l+1;++i)
{
j=i+l-1;
m[i][j]=inf;
for(int k=i;k<=j-1;++k)
{
int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
}
//输出最优解
void print_optimal_parens(int i,int j)
{
if(i==j)
cout<<"A"<<i;
else
{
cout<<"(";
print_optimal_parens(i,s[i][j]);
print_optimal_parens(s[i][j]+1,j);
cout<<")";
}
}
int main()
{
int p[]={30,35,15,5,10,20,25};
matrix_chain_order(p);
for(int i=1;i<=5;++i)
for(int j=6;j>=2;--j)
cout<<m[i][j]<<" ";
cout<<endl;
print_optimal_parens(1,6);
cout<<endl;
return 0;
}
3.最长公共子序列
给定两个序列<x1,x2..xm>,<y1,y2...yn>,找出他们最长的公共子序列LCS,时间复杂度O(mn)
#define M 7
#define N 6
int c[M+1][N+1];//c[i][j]为序列<x1,x2..xi>和<y1,y2..yi>的LCS,当i=0或j=0时为0;
void LCS_length(char *x,char *y)
{
int i,j;
for(i=1;i<=M;++i)
c[i][0]=0;
for(j=0;j<=N;++j)
c[0][j]=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;
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];
}
}
//构造一个LCS
void print_LCS(char *x,char *y,int i,int j)
{
if(i==0 || j==0)
return;
if(x[i]==y[j])
{
print_LCS(x,y,i-1,j-1);
cout<<x[i]<<" ";
}
else if(c[i-1][j]>=c[i][j-1])
print_LCS(x,y,i-1,j);
else
print_LCS(x,y,i,j-1);
}
int main()
{
char x[8]={'\0','A','B','C','B','D','A','B'};
char y[7]={'\0','B','D','C','A','B','A'};
LCS_length(x,y);
print_LCS(x,y,7,6);
cout<<endl<<c[7][6]<<endl;
return 0;
}
4.(1)O(n^2)时间找出最长单调递增子序列,只需将序列按递增排序然后和原序列找LCS
(2)O(nlgn)时间找出最长单调递增子序列
int find(int *a,int len,int n)//修改后的二分查找,若返回值为 x,则 a[x]>=n
{
int left=0,right=len,mid=(left+right)/2;
while(left<=right)
{
if(n>a[mid]) left=mid+1;
else if(n<a[mid]) right=mid-1;
else return mid;
mid=(left+right)/2;
}
return left;
}
int main()
{
int n,a[100],c[100],i,j,len;//新开一变量 len,用来储存每次循环结束后 c 中已经求出值的元素的最大下标
while(cin>>n)
{
for(i=0;i<n;i++)
cin>>a[i];
c[0]=-1;
c[1]=a[0];
len=1;//此时只有 c[1]求出来,最长递增子序列的长度为 1.
for(i=1;i<n;i++)
{
j=find(c,len,a[i]);
c[j]=a[i];
if(j>len)//要更新 len,另外补充一点:由二分查找可知 j 只可能比 len 大 1
len=j;//更新 len
}
cout<<len<<endl;
}
return 0;
}
5.最优二叉查找树
#define N 6 #define inf 65535 float e[N+1][N+1];//e[i][j]为搜索一棵包含关键字ki...kj的最优二叉查找树的期望代价 float w[N+1][N+1];//w[i][j]表示一棵树成为一个结点的子树时,子树每个结点深度增加1所带来的搜索代价 int root[N][N];//root[i][j]是包含关键字ki...kj的一棵最优二叉查找树的根 void optimal_bst(float *p,float *q) { int i,j,l,r; float t; for(i=1;i<=N;++i) { e[i][i-1]=q[i-1]; w[i][i-1]=q[i-1]; } for(l=1;l<=N-1;++l) { for(i=1;i<=N-l;++i) { j=i+l-1; e[i][j]=inf; w[i][j]=w[i][j-1]+p[j]+q[j]; for(r=i;r<=j;++r) { t=e[i][r-1]+e[r+1][j]+w[i][j]; if(t<e[i][j]) { e[i][j]=t; root[i][j]=r; } } } } } //输出结果 void construct_optimal_bst(int i,int j) { if(i==1 && j==N-1) cout<<"k"<<root[i][j]<<" is root"<<endl; if(i<j) { cout<<"k"<<root[i][root[i][j]-1]<<" is leftchild of "<<"k"<<root[i][j]<<endl; construct_optimal_bst(i,root[i][j]-1); if(root[i][j]!=j) cout<<"k"<<root[root[i][j]+1][j]<<" is rightchild of "<<"k"<<root[i][j]<<endl; construct_optimal_bst(root[i][j]+1,j); } if(i==j) { cout<<"d"<<i-1<<" is leftchild of "<<"k"<<i<<endl; cout<<"d"<<i<<" is rightchild of "<<"k"<<i<<endl; } if(i>j) cout<<"d"<<j<<" is rightchild of "<<"k"<<j<<endl; } int main() { float p[6]={0,0.15,0.1,0.05,0.1,0.2}; float q[6]={0.05,0.1,0.05,0.05,0.05,0.1}; optimal_bst(p,q); construct_optimal_bst(1,5); return 0; }
Knuth has shown that there are always roots of optimal
subtrees such that root[i,j-1]<=root[i,j]<=root[i+1,j] f all
1<=i<=n. Use this fact to modify the OPTIMAL-BST procedure to run
in Θ(n^2) time.
——————————————————————————————————————————————————
First prove this fact. Consider the optimal BST T[i+1,j] which has
nodes i+1 to j. Inserting a i node to T(i.e. i as i+1""s left child,
proper adjustment to dummy nodes) makes also a legal BST T""[i,j].
If i+1""s height is h, adding a i node leads to an increase of search
cost by (h+1)*p[i]+(h+2)*q[i-1]+q[i]. When constructing the optimal BST
T[i,j], if root[i,j] > root[i+1,j], then root[i+1,j](in T[i,j]) must
appear in the root[i,j]""s left subtree. Since i+1""s depth, with
respective to root[i+1,j] in T[i,j] is identical to that in T[i+1,j].
The actual i""s depth, i.e. with respective to T[i,j]""s root, root[i,j],
is thus larger. But, we have another optimal tree T[i,j], which as a
less increasing cost when ing node i. Thus, T[i+1,j] plus node i-1
can make a better tree, which contradicts T[i,j]""s optimism. Therefe,
root[i,j]<=root[i+1,j]. Similarly, root[i,j-1]<=root[i,j].
Thus, we can modify the fmula to e[i,j] =
min{root[i,j-1]<=r<=root[i+1,j],e[i,r-1]+e[r+1,j]+w(i,j)}. Then
we""re to prove that the calculating of this fmula, using dynamic
programming, takes Θ(n^2) time. we call the group of states e[i,j] with
the fixed j-i (=k) the level-k group(obviously there""re n-k nodes in the
group). the calculation of e[i,j] takes root[i+1,j]-root[i,j-1]+1
iterations. thus, f all level-k group states, their calculations takes
root[k,1]-root[1,k]+n-k iterations in all. Since
1<=root[k,1],root[1,k]<=n, the number of iterations is thus Θ(n).
And the k varies 0 to n-1. Thus the overall complexity is Θ(n)*n =
Θ(n^2). This is a common trick to optimize a Θ(n^3) dp algithm f
some kind of problems into a Θ(n^2) one.