聊聊数据结构与算法:动态规划
背包问题
背包问题(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