用动态分析解决0-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]，依次类推。
代码实现
| 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 | #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]。
所以代码如下：
| 1 2 3 4 5 6 7 8 9 | 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]); } |
我们可以缩小范围，因为只有当购物车的容量大于等于物品重量的时候才要更新，所以代码如下：
| 1 2 3 4 5 6 7 8 9 | 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
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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]=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 |
代码实现
| 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 | 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)。
| 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 | 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); } } |
动态规划算法总结
动态规划关键总结如下：
- 最优子结构判定
- 做出一个选择。
- 假定已经知道了哪种选择是最优的。
- 最优的会产生哪些子问题。
- 证明原问题的最优解包含其子问题的最优解。
- 如何得到最优解递归式
- 分析原问题最优解和子问题最优解的关系。
- 考察有多少种选择。
- 得到最优解递归式。
