2019-02-22 178 views 评论

解析动态规划问题（3）

用动态分析解决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[][]	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0
1	6	6	6	6	6	6	6	6	6
2	6	6	6	6	6	9	9	9	9
3	6	6	6	6	11	11	11	11	11
4	6	6	10	10	11	11	15	15	15
5	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 &lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;algorithm&gt;
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 &lt;&lt; "请输入物品的个数 n:";
    cin &gt;&gt; n;
    cout &lt;&lt; "请输入购物车的容量W:";
    cin &gt;&gt; W;
    cout &lt;&lt; "请依次输入每个物品的重量w和价值v，用空格分开:";
    for(i=1;i&lt;=n;i++)
        cin&gt;&gt;w[i]&gt;&gt;v[i];
    for(i=1;i&lt;=n;i++)//初始化第0列为0
        c[i][0]=0;
    for(j=1;j&lt;=W;j++)//初始化第0行为0
        c[0][j]=0;
    for(i=1;i&lt;= n;i++)//计算c[i][j]
        for(j=1;j&lt;=W;j++)
            if(j&lt;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&lt;&lt;"装入购物车的最大价值为:"&lt;&lt;c[n][W]&lt;&lt;endl;

    //用于测试
    for (i=1; i&lt;=n; i++ )
    {
        for (j=1; j&lt;=W; j++ )
          cout &lt;&lt; c[i][j]&lt;&lt;"\t" ;
        cout &lt;&lt; endl;
    }
    cout &lt;&lt; endl;

    //逆向构造最优解
    j=W;
    for(i=n;i&gt;0;i--)
        if(c[i][j]&gt;c[i-1][j])
        {
            x[i]=1;
            j-=w[i];
        }
        else
            x[i]=0;
    cout&lt;&lt;"装入购物车的物品序号为:";
    for(i=1;i&lt;=n;i++)
        if(x[i]==1)
           cout&lt;&lt;i&lt;&lt;"  ";
    return 0;
}

#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&lt;=n;i++)
        for(j=W;j&gt;0;j--)
            if(j&gt;=w[i])  //当物品的重量大于购物车的容量，
            //比较此物品放与不放是否能使得购物车内的价值最大
              dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}

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&lt;= n;i++)
        for(j=W;j&gt;=w[i];j--)
      //当物品的重量大于购物车的容量
 //比较此物品放与不放是否能使得购物车内的价值最大
           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&lt;=n;i++)
        sum[i]=sum[i-1]+w[i];
     for(i=1;i&lt;=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&gt;=bound;j--)
            //当物品的重量大于购物车的容量
            //比较此物品放与不放是否能使得购物车内的价值最大
           dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
     }
}

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[][]	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&lt;=n+1;i++)
    {
        c[i][i-1]=0.0;
        w[i][i-1]=q[i-1];
    }
    for(int t=1;t&lt;=n;t++)//t为关键字的规模
        //从下标为i开始的关键字到下标为j的关键字
        for(i=1;i&lt;=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&lt;=j;k++)
            {
                double temp=c[i][k-1]+c[k+1][j];
                if(temp&lt;c[i][j]&amp;&amp;fabs(temp-c[i][j])&gt;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&lt;&lt;"S"&lt;&lt;s[i][j]&lt;&lt;" 是根"&lt;&lt;endl;
        flag=1;
    }
    int k=s[i][j];
    //如果左子树是叶子
    if(k-1&lt;i)
    {
        cout&lt;&lt;"e"&lt;&lt;k-1&lt;&lt;" is the left child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
    }
    //如果左子树不是叶子
    else
    {
        cout&lt;&lt;"S"&lt;&lt;s[i][k-1]&lt;&lt;" is the left child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
        Construct_Optimal_BST(i,k-1,1);
    }
    //如果右子树是叶子
    if(k&gt;=j)
    {
        cout&lt;&lt;"e"&lt;&lt;j&lt;&lt;" is the right child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
    }
    //如果右子树不是叶子
    else
    {
        cout&lt;&lt;"S"&lt;&lt;s[k+1][j]&lt;&lt;" is the right child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
        Construct_Optimal_BST(k+1,j,1);
    }
}

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&lt;=n+1;i++)
    {
        c[i][i-1]=0.0;
        w[i][i-1]=q[i-1];
    }
    for(int t=1;t&lt;=n;t++)//t为关键字的规模
        //从下标为i开始的关键字到下标为j的关键字
        for(i=1;i&lt;=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]&gt;i?s[i][j-1]:i;
            int j1=s[i+1][j]&lt;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&lt;=j1;k++)
            {
                double temp=c[i][k-1]+c[k+1][j];
                if(temp&lt;c[i][j]&amp;&amp;fabs(temp-c[i][j])&gt;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&lt;&lt;"S"&lt;&lt;s[i][j]&lt;&lt;" 是根"&lt;&lt;endl;
        flag=1;
    }
    int k=s[i][j];
    //如果左子树是叶子
    if(k-1&lt;i)
    {
        cout&lt;&lt;"e"&lt;&lt;k-1&lt;&lt;" is the left child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
    }
    //如果左子树不是叶子
    else
    {
        cout&lt;&lt;"S"&lt;&lt;s[i][k-1]&lt;&lt;" is the left child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
        Construct_Optimal_BST(i,k-1,1);
    }
    //如果右子树是叶子
    if(k&gt;=j)
    {
        cout&lt;&lt;"e"&lt;&lt;j&lt;&lt;" is the right child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
    }
    //如果右子树不是叶子
    else
    {
        cout&lt;&lt;"S"&lt;&lt;s[k+1][j]&lt;&lt;" is the right child of "&lt;&lt;"S"&lt;&lt;k&lt;&lt;endl;
        Construct_Optimal_BST(k+1,j,1);
    }
}