用动态分析解决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[][]012345678910
000000000000
100666666666
200666669999
30066661111111111
4006610101111151515
5006610121216161717

所以最大价值为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.算法复杂度分析
(1)时间复杂度:O(nW)
(2)空间复杂度O(n
W)
2.算法优化改进
使用一个数组dp[]保证第i次循环结束后dp[j]中表示的就是我们定义的c[i][j]。
所以代码如下:

我们可以缩小范围,因为只有当购物车的容量大于等于物品重量的时候才要更新,所以代码如下:

我们还可以再缩小范围,确定搜索的下界bound

快速定位—最优二叉搜索树(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[][]0123456
10.060.180.370.520.590.761.00
20.080.270.420.490.660.90
30.100.250.320.490.73
40.070.140.310.55
50.050.220.46
60.050.29
70.10
c[][]0123456
100.180.550.951.231.762.52
200.270.670.901.382.09
300.250.460.941.48
400.140.450.98
500.220.68
600.29
70
s[][]0123456
1122235
222335
33335
4455
556
66
7

代码实现

复杂度分析及改进

时间复杂度为O(n3),空间复杂度为O(n2)。
又可以用四边形不等式优化(后续研究一下)
时间复杂度减少到O(n2)。

动态规划算法总结

动态规划关键总结如下:

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