聊聊数据结构与算法：动态规划
背包问题
背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
如果限定每种物品只能选择0个或者1个，则问题称为0-1背包问题。如果限定物品最多只能选择多少个，则问题称为有界背包问题。如果不限定每种物品的数量，则问题称为无界背包问题。各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解，所以我们讨论的更多是0-1背包问题。
假设题目是：背包可装总重量为4的物品，有3件物品，分别是音响（重量4，价值3000元）、笔记本（重量3，价值2000元），吉他（重量1，价值1500元），如何选择才能使物品总价值最高？
既然背包问题是一个NP完全问题，那么就不存在一种多项式时间算法。随着背包大小和物品数量的增加，穷举所有的物品组合来找到最优解并不可取。或许我们可以选择近似算法，采用贪心策略，每次装入价值最高的物品，但结果是，优先选择了价值最高的音响后再也装不下其他物品，总价值为3000元，这是一个近似最优解。而这道题的最优解明显是笔记本+吉他，总价值为3500元。
但是背包问题有趣的地方在于，它存在一个伪多项式时间算法，比穷举效率更高的求最优解算法，即动态规划算法。
动态规划
动态规划使用一个表格，行是可选择的物品，列是不同容量的背包，表格如下：
物品\背包容量 1 2 3 4
吉他
音响
笔记本
在第1行，只有吉他可以选择，因此1~4容量的背包可组合的最大价值都是1500元，表格如下：
物品\背包容量 1 2 3 4
吉他 1500（吉他） 1500（吉他） 1500（吉他） 1500（吉他）
音响
笔记本
在第2行，可以选择的物品有吉他和音响，音响的重量是4，只有在背包容量为4的时候才能选择，因此第2行的前3列最大价值都是1500元，第4列的最大价值是3000元，表格如下：
物品\背包容量 1 2 3 4
吉他 1500（吉他） 1500（吉他） 1500（吉他） 1500（吉他）
音响 1500（吉他） 1500（吉他） 1500（吉他） 3000（音响）
笔记本
以此类推，在第3行的第4列时，情况比较特殊，表格如下：
物品\背包容量 1 2 3 4
吉他 1500（吉他） 1500（吉他） 1500（吉他） 1500（吉他）
音响 1500（吉他） 1500（吉他） 1500（吉他） 3000（音响）
笔记本 1500（吉他） 1500（吉他） 2000（笔记本) ?
通过表格已知此前背包容量为4的最大价值是3000元（第2行第4列），但此时有笔记本可以选择，并且笔记本重量只有3，也就是还剩余重量1的容量，通过查询表格可知容量为1的最大价值是1500元（第3行第1列），3000+1500 > 3000，所以最大价值是3500元（笔记本+吉他），最终表格如下：
物品\背包容量 1 2 3 4
吉他 1500（吉他） 1500（吉他） 1500（吉他） 1500（吉他）
音响 1500（吉他） 1500（吉他） 1500（吉他） 3000（音响）
笔记本 1500（吉他） 1500（吉他） 2000（笔记本) 3500（笔记本+吉他）
这就是动态规划算法，动态规划属于分治思想，它将一个大问题划分成多个子问题，先解决子问题，把子问题的答案记录在一个表内，最后根据这些答案逐步解决大问题。动态规划的代码实现举例如下：
public static void main(String[] args) {
// 物品的价值数组
int val[] = {1500, 3000, 2000};
// 物品的重量数组
int wt[] = {1, 4, 3};
// 背包容量
int W = 4;
System.out.println(knapsack(val, wt, W));
}
public static int knapsack(int val[], int wt[], int W) {
// 得到物品数量，可以是重量数组长度也可以是价值数组长度
int N = wt.length;
// 创建一个二维数组，即一个表格
// 第1行和第1列分别保存物品数量为0与背包容量为0的情况
int[][] V = new int[N + 1][W + 1];
// 当背包容量为0时，第一列的数据都为0
for (int col = 0; col <= W; col++) {
V[0][col] = 0;
}
// 当物品数量为0时，第一行的数据都为0
for (int row = 0; row <= N; row++) {
V[row][0] = 0;
}
for (int item=1;item<=N;item++){
for (int weight=1;weight<=W;weight++){
if (wt[item-1]<=weight){
// 如果当前的容量装得下当前物品
// 则比较 当前物品价值+剩余容量的最大价值 和 之前相同容量的最大价值
// 最大价值为上述两个值的最大值
V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
}
else {
// 如果当前的容量装不下当前物品
// 则最大价值为相同容量的最大价值(即上一行)
V[item][weight]=V[item-1][weight];
}
}
}
return V[N][W];
}
伪多项式时间算法
前面说到动态规划是一个伪多项式时间算法（Pseudo-polynomial time algorithm），那什么是伪多项式时间算法？
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值规模N的多项式，但其运行时间与输入数值规模N的二进制位数呈指数增长关系，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。
这段话怎么理解？动态规划算法的时间复杂度是O(nW)，其中n是物品的个数，W是背包的最大容量。这是一个多项式时间算法，可我们知道背包问题是一个NP完全问题，目前并不存在多项式时间算法，哪里错了？
其实是这样，从数值大小考虑，算法的复杂度取决于n和W的值，是O(nW)的。但是如果从输入规模考虑情况就不一样了，输入规模可以理解为输入到该算法的数据占了多少比特的内存。比如说背包的最大容量W，占用的比特数为L，因为是二进制，所以log2(W)=L，则O(nW)=O(n*2^L)，因此可见，该算法的复杂度与输入规模L呈指数关系，这就是伪多项式时间算法。
- 多项式时间算法：算法的复杂度与输入的数值大小和输入的规模都呈多项式关系
- 伪多项式时间算法：算法的复杂度与输入规模呈指数关系，与输入的数值大小呈多项式关系。
这里还延伸出了一个概念，就是一般将关于输入的数值大小的时间复杂度称为传统时间复杂度，将关于输入规模的时间复杂度称为标准时间复杂度。所以如果一个算法的传统时间复杂度是多项式时间的，而标准时间复杂度不是多项式时间的，则我们称这个算法是伪多项式时间的。
一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为强NP完全问题。
参考文档
http://www.importnew.com/13072.html