特征
动态规划和分治算法类似
,基本思想都是将待求的问题分解成若干个子问题
,先求解子问题
,
然后从这些子问题的解得到原问题的解
和分治算法不同的是
,动态规划求解的问题经过分解得到的子问题往往不是相互独立的
,
如果用分治算法解这类问题
,则分解得到的子问题的数量太多
,以至于最后解决原问题需要消耗指数的时间
动态规划用一个表来记录所有已经解决的子问题的答案
,下次需要就直接拿来用就行
通常动态规划有这样的步骤
:
1.找出最优解的性质
,刻画它的结构特征
2.递归定义最优值
3.以自底向上的方式计算出最优值
4.根据最优值构造最优解
矩阵连乘问题
矩阵连乘问题描述：给定n个矩阵｛A1
, A2
, …
, An｝，
Ai的维数为pi
-1×pi，Ai与Ai
+1是可乘的，i
=1,2 ,…
,n
-1。
如何确定计算矩阵连乘积的计算次序，
使得依此次序计算矩阵连乘积需要的数乘次数最少。
package guoyihui
.four
;
public class Matrix
{
public static int m
[][];
public static int p
[];
public static int s
[][];
public static void main(String
[] args
)
{
p
= new int[]{ 5, 200, 2, 100, 30, 200 };
int number
=p
.length
-1;
m
= new int[number
+1][number
+1];
s
= new int[number
+1][number
+1];
String
[] str
=new String[]{"","A1","A2","A3","A4","A5"};
matrixChain(p
, m
, s
);
traceback(s
, 1, 5, str
);
for (String string
: str
)
{
System
.out
.print(string
+" ");
}
}
public static void matrixChain(int[] p
,int[][] m
,int[][] s
)
{
int n
=p
.length
-1;
for(int x
=1;x
<=n
;x
++)
{
m
[x
][x
]=0;
}
for(int len
=2;len
<=n
;len
++)
{
for(int start
=1;start
<=n
-len
+1;start
++)
{
int end
=start
+len
-1;
m
[start
][end
]=m
[start
+1][end
]+p
[start
-1]*p
[start
]*p
[end
];
s
[start
][end
]=start
;
int temp
;
for(int index
=start
+1;index
<end
;index
++)
{
temp
=m
[start
][index
]+m
[index
+1][end
]+p
[start
-1]*p
[index
]*p
[end
];
if(m
[start
][end
]>temp
)
{
m
[start
][end
]=temp
;
s
[start
][end
]=index
;
}
}
}
}
}
public static void traceback(int[][] s
,int start
,int end
,String
[] str
)
{
if(start
==end
)
{
return;
}
if(start
<s
[start
][end
])
{
str
[start
] ="("+str
[start
];
str
[s
[start
][end
]] +=")";
}
traceback(s
, start
, s
[start
][end
],str
);
if(s
[start
][end
]+1<end
)
{
str
[s
[start
][end
]+1] ="("+str
[s
[start
][end
]+1];
str
[end
] +=")";
}
traceback(s
, s
[start
][end
]+1, end
,str
);
}
}
最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
确切地说，给定序列X={x1, x2, …, xm}，若存在一个严格递增下标序列{i1, i2, …, ik}
使得对于所有j=1,2,…,k有：zj=xij，则序列Z={z1, z2, …, zk}是X的子序列。
给定两个序列X=｛A,B,C,B,D,A,B｝和Y={B,D,C,A,B,A}，
当另一序列Z={B,D}既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
Z={B,C,B,A}是比{B,D}更长的子序列，它的长度为4，
因为X和Y没有长度大于4的公共子序列，
所以Z ={B,C,B,A}是X和Y的最长公共子序列。
1.找出最长公共子序列问题最优解性质，并刻划其结构特征。
1)若xm=yn = zk，则Zk-1是Xm-1和Yn-1的最长公共子序列。
2)若xm≠yn且zk≠xm(zk=yn)，则Z是Xm-1和Y的最长公共子序列。
3)若xm≠yn且zk≠yn(zk=xm)，则Z是X和Yn-1的最长公共子序列。
2. 子问题的递归结构
由最长公共子序列问题的最优子结构性质建立子问题最优值c[i][j]的递归关系。
当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。
其它情况下，由最优子结构性质可建立递归关系如下：
c[i][j]=0 i=0,j=0
c[i][j]=c[i-1][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
A先生找到了其失散多年的兄弟。为了确定血缘关系，A先生决定做DNA鉴定。
请编写程序，比较两组基因，
A先生基因片段为{A,C,T,C,C,T,A,G}，
A先生兄弟基因片段为{C,A,T,T,C,A,G,C}，
找出两人基因片段中最长相同的部分（最长公共子序列）。
采用动态规划策略解决该问题。
package jane
;
public class Jane
{
public static void main(String
[] args
)
{
char[] A
="ACTCCTAG".toCharArray();
char[] B
="CATTCAGC".toCharArray();
int[][] mark
=new int[A
.length
+1][B
.length
+1];
int[][] path
=new int[A
.length
+1][B
.length
+1];
for(int x
=1;x
<mark
.length
;x
++)
{
for(int y
=1;y
<mark
[x
].length
;y
++)
{
if(A
[x
-1]==B
[y
-1])
{
mark
[x
][y
]=mark
[x
-1][y
-1]+1;
path
[x
][y
]=1;
}
else if(mark
[x
-1][y
]>mark
[x
][y
-1])
{
mark
[x
][y
]=mark
[x
-1][y
];
path
[x
][y
]=2;
}
else
{
mark
[x
][y
]=mark
[x
][y
-1];
path
[x
][y
]=3;
}
}
}
int x
=path
.length
-1,y
=path
[0].length
-1;
String SubString
="";
while(x
!=0 && y
!=0)
{
if(path
[x
][y
]==1)
{
SubString
=A
[x
-1] +SubString
;
x
--;y
--;
}
else if(path
[x
][y
]==2)
x
--;
else
y
--;
}
System
.out
.println(SubString
);
}
}
动态规划算法的基本要素
从计算矩阵连乘积最优计算次序的动态规划算法可以看出，
该算法的有效性依赖于问题本身所具有的两个重要性质：
最优子结构性质和子问题重叠性质。
1、最优子结构
设计动态规划算法的第1步通常是要刻画最优解的结构。
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。
在矩阵连乘积最优计算次序问题中注意到，若A1A2…An的最优完全加括号方式
在AK和AK+1之间将矩阵链断开，
则由此确定的子链A1A2…Ak和Ak+1，Ak+2…An的完全加括号方式也最优，
即该问题具有最优子结构性质。
在分析该问题的最优子结构性质时，首先假设由问题的最优解导出的
其子问题的解不是最优的，然后再设法说明在这个假设下可
构造出比原问题最优解更好的解，从而导致矛盾。
在动态规划算法中，利用问题的最优子结构性质，
可以以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
2. 重叠子问题
可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。
动态规划算法每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，
而后将其解保存在一个表格中，当再次需要解此子问题时，
只是简单地用常数时间查看一下结果。
通常，不同的子问题个数随问题的大小呈多项式增长。
因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。
最优二叉搜索树
设S
={x1
, x2
, ..., xn
}是一个有序集，例如S
={1, 2, 3, 4, 5, 6, 7}。
表示有序集S的二叉搜索树利用二叉树的结点存储有序集中的元素。
二叉树是每个结点最多有两个子树的树结构。
每个结点有一个左子结点
(Left children
)和右子结点
(Right children
)。
左子结点是左子树的根结点，右子结点是右子树的根结点。
二叉搜索树 （Binary Search Tree
)：每个结点都不比它左子树的任意元素小，
而且不比它的右子树的任意元素大。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树 。
二叉搜索树的叶结点是形如
(xi，xi
+1)的开区间。
在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形：
在二叉搜索树的内结点中找到x
=xi。
在二叉搜索树的叶结点中确定x∈
(xi，xi
+1)，约定x0
=-∞，xn
+1=+∞。
设第一种情形中找到元素x
= xi的概率为bj；
在第二种情形中确定x∈
(xi，xi
+1)的概率为ai。
(a0
, b1
, a1
,...,bn
, an
)称为集合S的存取概率分布。
在表示S的二叉搜索树T中，设存储元素xi的结点层次为ci；
存储叶结点
(xi，xi
+1)的结点层次为dj，
则P表示在二叉搜索树T中作一次搜索所需要的平均比较次数。
P又称为二叉搜索树T的平均路长。
最优子结构性质
递归计算最优值
最优二叉搜索树Tij的路长为Pij，
由最优二叉搜索树问题的最优子结构性质可建立计算Pij的递归式如下：
记wi
,jpi
,j为
m(i
,j
)，计算
m(i
,j
)的递归式为
:
代码
package guoyihui
.mine
;
public class BestBinarySearchTree
{
public static String
[] n
= {"n1","n2","n3"};
public static void main(String
[] args
)
{
double[] b
={0.5, 0.1, 0.05};
double[] a
={0.15, 0.1, 0.05, 0.05};
double[][] m
=new double[b
.length
+2][b
.length
+1];
int[][] s
=new int[b
.length
+2][b
.length
+1];
double[][] w
=new double[b
.length
+2][b
.length
+1];
bestBinarySearchTree(a
, b
, m
, s
, w
);
int x
=1,y
=n
.length
;
printNode(s
, x
, y
);
}
public static void printNode(int[][] s
,int x
,int y
)
{
int temp
=s
[x
][y
];
System
.out
.println(n
[x
-1]+"-->"+n
[y
-1]+":的根节点"+n
[temp
-1]);
if(x
<=temp
-1)
{
printNode(s
, x
, temp
-1);
}
if(y
>=temp
+1)
{
printNode(s
, temp
+1, y
);
}
}
public static void bestBinarySearchTree(double[] a
,double[] b
,double[][] m
,int[][] s
,double[][] w
)
{
for(int x
=0;x
<b
.length
;x
++)
{
w
[x
+1][x
]=a
[x
];
m
[x
+1][x
]=0;
}
for(int r
=0;r
<=b
.length
;r
++)
{
for(int x
=1;x
<=b
.length
-r
;x
++)
{
int y
=x
+r
;
w
[x
][y
]=w
[x
][y
-1]+a
[y
]+b
[y
-1];
m
[x
][y
]=m
[x
][x
-1]+m
[x
+1][y
];
s
[x
][y
]=x
;
for(int k
=x
+1;k
<=y
;k
++)
{
double temp
=m
[x
][k
-1]+m
[k
+1][y
];
if(temp
<m
[x
][y
])
{
m
[x
][y
]=temp
;
s
[x
][y
]=k
;
}
}
m
[x
][y
]+=w
[x
][y
];
}
}
}
}
电路布线
电路布线问题也被称为最大不相交子集问题（Maximum Noncrossing Subset，MNS）。
在一块电路板的上、下
2端分别有n个接线柱。
根据电路设计，要求用导线
(i
,π
(i
))将上端接线柱与下端接线柱相连，
导线
(i
,π
(i
))称为该电路板上的第i条连线。其中π
(i
)是
{1,2,…
,n
}的一个排列，图所示：
i
= ｛
1，
2，
3，
4，
5，
6，
7，
8，
9 ，
10｝
π
(i
) = ｛
8，
7，
4，
2，
5，
1，
9，
3，
10，
6 ｝
制作电路板时，要求将这n条连线分布到若干绝缘层上，
注意当且仅当两条连线之间无交叉，连线才可以设在同一层。
对于任何
1≤i
<j≤n，第i条连线和第j条连线不相交的充分且必要的条件是π
(i
)<π
(j
)。
电路板的第一层被称为优先层，在优先层中可以使用更细的连线，
因此其电阻也比其它层要小得多。
电路布线问题就是要确定怎样在第一层中尽可能多地布设导线，
即确定导线集Nets
={(i
,π
(i
)),1≤i≤n
} 的最大不相交子集。
记
N(i
,j
)={t
|(t
,π
(t
))∈Nets
, t≤i
, π
(t
)≤j
}，
N(i
, j
)的最大不相交子集为
MNS(i
, j
)，
Size(i
, j
)=|MNS(i
, j
)|。
所以
N(i
,j
)代表的就是上面第i个接口和下面第j个接口如果有线连接的时候
在其左边的最大的不相交的子集是什么
size(i
,j
)就是最大的不相交的子集有多少个
找出最优解的性质，并刻划其结构特征
(1)当i
=1时
(2)当i
>1时
这里拿
(7,9)来做例子
j
<π
(i
)
就是这些接口互相之间是没有线进行连接的
此时，
(i
,π
(i
)) ∉
N(i
, j
)。故在这种情况下：
N(i
, j
)=N(i
-1, j
)，
MNS(i
, j
)= MNS(i
-1, j
)，从而
Size(i
, j
)=Size(i
-1, j
)。
j≥π
(i
)
还是
(7,9)为例子
:
若
(i
, π
(i
))∈
MNS(i
, j
)，
对任意
(t
,π
(t
)) ∈
MNS(i
,j
)有t
<i且π
(t
)<π
(i
)。
在这种情况下
MNS(i
, j
)-{(i
,π
(i
))}是
N(i
-1,π
(i
)-1)的最大不相交子集，
否则，MNS
(i
-1,π
(i
)-1) ∪
{(i
,π
(i
))}⊆
N(i
, j
)是
比
MNS(i
, j
)更大的
N(i
, j
)的不相交子集。
这与
MNS(i
, j
)的定义相矛盾。则
MNS(i
, j
)= MNS
(i
-1,π
(i
)-1) +{(i
,π
(i
))}
Size(i
, j
)=Size(i
-1,π
(i
)-1)+1
上面就是说
将
(7,9)这条线加入到最大不相交子集里面
(7,9)的最大不相交子集是
(6,8)的最大不相交子集加上
(7,9)这条线
j≥π
(i
)
这里
(10,6)做例子
:
若
(i
, π
(i
))∉
MNS(i
, j
)，则对任意
(t
, π
(t
)) ∈
MNS(i
, j
)有t
<i。
从而，
MNS(i
, j
) ⊆
N(i
-1, j
)，
因此，
Size(i
, j
)≤
Size(i
-1, j
)。
另外，
MNS(i
-1, j
) ⊆
N(i
, j
)，故又有
Size(i
-1, j
) ≤
Size(i
, j
)从而，
Size(i
, j
)=Size(i
-1, j
)。
上面就是说不要将
(10,6)这条线加入到集合里面
,
(10,6)的最大不相交子集是
(6,5)的最大不相交子集
递归定义最优值
代码
package guoyihui
.mine
;
public class CircuitWiring
{
public static int n
;
public static void main(String
[] args
)
{
int[] c
= {0,6,8,12,2,1,4,5,3,11,7,10,9,13};
n
=c
.length
-1;
int[][] size
=new int[n
+1][n
+1];
MNS(c
, size
);
System
.out
.println(size
[n
][n
]);
int[] temp
=new int[n
];
int tarceBack
= tarceBack(size
, c
, temp
);
for(int x
=0;x
<tarceBack
;x
++)
{
System
.out
.println("加入第"+temp
[x
]+"条线");
}
}
public static int tarceBack(int[][] size
,int[] c
,int[] temp
)
{
int y
=n
;
int index
=0;
for(int x
=n
;x
>=1;x
--)
{
if(size
[x
][y
]!=size
[x
-1][y
])
{
temp
[index
++]=x
;
y
=c
[x
]-1;
}
}
return index
;
}
public static void MNS(int[] c
,int[][] size
)
{
for(int j
=0;j
<=c
[1];j
++)
{
size
[1][j
]=0;
}
for(int j
=c
[1];j
<=n
;j
++)
{
size
[1][j
]=1;
}
for(int x
=2;x
<=n
;x
++)
{
for(int j
=0;j
<c
[x
];j
++)
{
size
[x
][j
]=size
[x
-1][j
];
}
for(int j
=c
[x
];j
<=n
;j
++)
{
size
[x
][j
]=Math
.max(size
[x
-1][j
], size
[x
-1][c
[x
]-1]+1);
}
}
}
}
0-1背包问题
问题提出：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。
例如
, 有
3个物品，w
={7, 8, 9}, v
={20, 25, 30} , C
=16。
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大
?
0-1背包问题物品i在考虑是否装入背包时都只有两种选择，
不装入背包或装入背包，即xi ∈
{𝟎
,𝟏
}。
不能将物品i装入背包多次，也不能只装入部分的物品i。
此问题的形式化描述是：
给定C
>0, wi
>0, vi
>0,1≤i≤n
,
要求找出n元
0-1向量（ x1
, x2
, …
, xn ）
, xi ∈
{𝟎
,𝟏
}, 1≤i≤n
,使得
最优子结构性质
建立递归关系
代码
package guoyihui
.mine
;
public class PackageProblem
{
public static int n
;
public static void main(String
[] args
)
{
int[] w
= {0,5,4,8,6,9};
int[] v
={0,20,6,8,15,18};
int c
=18;
n
=w
.length
-1;
int[][] m
=new int[n
+1][c
+1];
packageProblem(v
, w
, m
, c
);
System
.out
.println("最大价值: "+m
[1][c
]);
int[] temp
=new int[n
+1];
traceback(m
, w
, c
, temp
);
for(int x
=1;x
<temp
.length
;x
++)
{
if(temp
[x
]==1)
{
System
.out
.println("背包放入了:"+w
[x
]);
}
}
}
public static void packageProblem(int[] v
,int[] w
,int[][] m
,int c
)
{
int jMax
=Math
.min(w
[n
]-1, c
);
for(int j
=0;j
<=jMax
;j
++)
{
m
[n
][j
]=0;
}
for(int j
=w
[n
];j
<=c
;j
++)
{
m
[n
][j
]=v
[n
];
}
for(int i
=n
-1;i
>=1;i
--)
{
jMax
=Math
.min(w
[i
]-1, c
);
for(int j
=0;j
<=jMax
;j
++)
{
m
[i
][j
]=m
[i
+1][j
];
}
for(int j
=w
[i
];j
<=c
;j
++)
{
m
[i
][j
]=Math
.max(m
[i
+1][j
], m
[i
+1][j
-w
[i
]]+v
[i
]);
}
}
}
public static void traceback(int[][] m
,int[] w
,int c
,int[] temp
)
{
for(int x
=1;x
<n
;x
++)
{
if(m
[x
][c
]==m
[x
+1][c
])
{
temp
[x
]=0;
}
else
{
temp
[x
]=1;
c
-=w
[x
];
}
}
temp
[n
] = m
[n
][c
]>0?1:0;
}
}
