动态规划、LCS、01背包问题

动态规划：将一个具有最优子结构性质的问题分成若干个子问题，在求解过程中，记录下子问题的结果，存储在一个表格中，使得公共的子问题只需要计算一次。书中给出的基本原理：动态规划将问题分成若干个相互重叠的子问题，递归的求解子问题，保存子问题的解，再将它们的解组合起来，求出原问题的解。使用动态规划必须满足两个条件：最优子结构和子问题重叠。问题的最优解由相关子问题的最优解组合而成，一个问题的最优解包含其子问题的最优解。

LCS：最长公共子序列；求两个给定序列的最长公共部分，必须是以相同的顺序出现，但是不必要是连续的。
设X = <x1,x2...xm>, Y = <y1,y2...yn>为两个序列，并设Z = <z1,z2...zk>为X和Y的任意一个LCS。可以得出：
1.如果xm = yn，那么zk = xm = yn而且Z(k-1)是X(m-1)和Y(n-1)的一个LCS；
2.如果xm != yn，那么zk != xm蕴含Z是X(m-1)和Y的一个LCS；
3.如果xm != yn，那么zk != yn蕴含Z是X和Y(n-1)的一个LCS。
注：上面的Z(k-1)表示序列Z<z1,z2...zn>,其中n=k-1。其它的X()和Y()也是一样的。
所以LCS具有最优子结构,也可以看出LCS问题中的重叠子问题的性质。所以我们可以用动态规划来解决LCS问题。由LCS问题的最优子结构可得出递归式：

Java代码实现：
Java
public List<Integer> lcs(List<Integer> a, List<Integer> b) {
List<Integer> rsList = new LinkedList<>();
int sizeA = a.size(), sizeB = b.size();
if (sizeA == 0 || sizeB == 0) {
return rsList;
}
if (a.get(sizeA - 1).equals(b.get(sizeB - 1))) {
int m = a.get(sizeA - 1);
List<Integer> subList = lcs(a.subList(0, sizeA - 1), b.subList(0, sizeB - 1));
subList.add(m);
return subList;
}
List<Integer> sub1 = lcs(a.subList(0, sizeA - 1), b);
List<Integer> sub2 = lcs(a, b.subList(0, sizeB - 1));
return sub1.size() > sub2.size() ? sub1 : sub2;
}

**01背包问题：**
背包问题是具有多种[复杂情况](http://blog.sina.com.cn/s/blog_8cf6e8d90100zldn.html)，这里仅举01背包为例。
*问题描述：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？？在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。 *
- 01背包问题的递归式：
令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则
```Java```
V(i,0)=V(0,j)=0 
V(i,j)=V(i-1,j)                            ;j<wi  
V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi)}      ;j>wi