关于最长公共子序列（LCS）

最长公共子序列和最长公共子串是有区别的，之前我一直把它们混淆。

1. 最长公共子串举例：假设S1={A,D,C,B,E,X,Q}，S2={H,P,D,C,B,E,M,L}
   那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。
   最长公共子序列。
2. 最长公共子序列举例：假设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，那么可以分以下三种情况讨论（具体每种情况证明不再累述）：

1. xm=yn=zk：那么Zk-1是Xm-1和Yn-1的LCS。
2. xm≠yn，yn≠zk：我们可以把yn去掉，那么Zk是Xm和Yn-1的LCS。
3. 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);
}

编辑距离

编辑距离和LCS的不同点

1. 编辑距离的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}
2. 构造最优解：编辑距离是从右下角开始，逆向查找d[i][j]的来源：上面表示需要删除，左侧表示需要插入；左上角要判断字符是否相等，若相等，不做任何操作，若不相等，执行替换。
3. 两者的时间复杂度都是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);
}

代码实现2：最贵的租金

其实只是把总结的递归式中的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	3

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(n³)

改进算法

最小值可以用四边形不等式来优化。
复杂度为O(n²)

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];
    }
}

用动态分析解决0-1背包问题

有n个物品，每个物品的重量为w[i]，价值为v[i]，购物车容量为W。选若干个物品放入购物车，在不超过容量的前提下使获得的价值最大。

问题分析

（1）分析最优解的结构特征
（2）建立具有最优值的递归式
可以对每个物品依次检查是否放入或者不放入，对于第i个物品的处理状态：用c[i][j]表示前i件物品放入一个容量为j的购物车可以获得的最大价值。

• 不放入第i件物品，x_i=0，装入购物车的价值不增加。那么问题就转化为“前i-1件物品放入容量为j的背包中”，最大价值为c[i-1][j]。
• 放入第i件物品，x_i=1，装入购物车的价值增加v_i。

那么问题就转化为了“前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<w_i）；
c[i][j]=max{c[i-1][j-w[i]]+v[i],c[i-1][j]}（当j>w_i）

算法设计

（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]);
     }
}

快速定位—最优二叉搜索树（OBST）

问题分析

递归表达式：
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]=q_i-1（j=i-1）；
w[i][j]=w[i][j-1]+p_j+q_j

算法设计

（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的{s_i}（j=i）的最优二叉搜索树的搜索成本c[i][j]，并记录最优策略，即树根s[i][j]，i=1,2,3,..,n。
• 按照递归式计算元素规模是2的{s_i,s_i+1}（j=i）的最优二叉搜索树的搜索成本c[i][j]，并记录最优策略，即树根s[i][j]，i=1,2,3,..,n-1。
• 以此类推，直到求出所有元素{s₁,s₂,…,s_n}的最优二叉搜索树的搜索成本c[1][n]和最优策略s[1][n]。

（4）构造最优解。

• 首先读取s[1][n]，令k=s[1][n]，输出s_k为最优二叉搜索树的根。
• 判断如果k-1<1，表示虚结点e_k-1是s_k的左子树；否则，递归求解左子树Construct_Optimal_BST(1,k-1,1)。
• 判断如果k≥n，表示虚结点e_k是s_k的右孩子。；否则，输出s[k+1][n]是s_k的右孩子，递归求解右子树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(n³)，空间复杂度为O(n²)。
又可以用四边形不等式优化（后续研究一下）
时间复杂度减少到O(n²)。

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);
    }
}

动态规划算法总结

动态规划关键总结如下：

1. 最优子结构判定
   • 做出一个选择。
   • 假定已经知道了哪种选择是最优的。
   • 最优的会产生哪些子问题。
   • 证明原问题的最优解包含其子问题的最优解。
2. 如何得到最优解递归式
   • 分析原问题最优解和子问题最优解的关系。
   • 考察有多少种选择。
   • 得到最优解递归式。